ST310 Course Project

The aim of this project is to demonstrate the use of machine learning techniques learnt in the ST310 Machine Learning module. We rely on both linear (Logistic Regression) and non-linear methods (Random Forests and Gradient Boosted Decision Trees) for a classification problem.

Remark: If executing this notebooks as a .Rmd file, ensure that all libraries and dependencies are installed and that the chunks are executed in sequential order.

Dataset

We have obtained data from the Kaggle March Tabular Playground competition. The data consists of anonymised features, which correspond to a binary outcome variable; in other words the task is a classification problem. Although the data is anonymised, the challenge description states:

The dataset is used for this competition is synthetic but based on a real dataset and generated using a CTGAN. The original dataset deals with predicting the amount of an insurance claim. Although the features are anonymized, they have properties relating to real-world features.

The dataset consists of 30 features, 19 categorical variables and 11 numerical variables., and a binary outcome variable target. 73.5% of the observations have ‘target==1,’ suggesting an imbalanced dataset. We will need to process these categorical variables in some manner, which we shall consider in subsequent sections.

library(tidyverse)
library(ggplot2)
library(patchwork)
library(broom)
library(tidymodels)
library(arm)
library(car) #outlier
library(tidyr)
library(glmnet)
library(caret)
library(randomForest)
library(xgboost)
library(catboost)
library(e1071)
library(data.table)
library(doParallel)
library(foreach)
library(pROC)
library(pdp)
df <- read.csv(file = "../data/train.csv")
cat(c("The dimensions of the array are :", dim(df)[1], ", ", dim(df)[2]))

The dataset consists of 30 features, 19 categorical variables and 11 numerical variables., and a binary outcome variable target. We will need to process these categorical variables in some manner, which we shall consider in the subsequent section.

A challenge is that we have no specific domain knowledge about the meaning of particular features, and whether they may be useful. Nonetheless, we can resort to model interpretability methods (Molnar, Christoph 2019) to obtain an ex-post explanation of our models. In the linear case, we can examine coefficients and their statistical significance, and in the case of tree-based models, we can utilise feature importances, partial dependence plots, and Shapley Values.

Preprocessing

We first remove the first column id, which represents an unique identifier for each observation. We then convert the first 19 columns, which are categorical variables into the factor data type in R, To reduce computational time, we subsample 4000 observations from the complete dataset of 300,000 observations. For our subsequent analysis, we will use only this subsample of 4000 observations, although the approaches can be extended to a larger dataset given greater computational resources. We further partition the 4000 observations, into a train set of 3000 observations and a test set of 1000 observations. All training and tuning are performed on the training data, and we will consider model performance on the test set performance scores.

Remark: Different models would require different preprocessing for the categorical variables, and thus we will further address in subsequent sections; for example the glm package can accept factors as a data type, whereas for glmnet they must be converted to the model.matrix format.

Remark: When encoding the categorical variables as dummy variables in our subsequent analysis, we find that there are over 600 unique categories across all 19 of the categorical variables. We could also consider different methods to process categorical variables, such as merging less frequently occuring categories, or target encoding (Parr, Terence and Howard, Jeremy 2019, ch. 6). Nonetheless, we stick with the factors and dummies approach given our lack of familiarity with these other methods.

cat_feats = 1:19 # the first 19 columns are categorical 
cont_feats <- 20:30 # and the next 11 are continuous
target_col <- 31 # target
# convert cats to factors
df <- column_to_rownames(df, var = "id") %>% 
         mutate_if(is.character,as.factor) %>% 
         mutate_at(vars(target), factor)
# subsample the data for faster model imputation
set.seed(1)
sam = sample(1:nrow(df), 4000)
df_sample = df[sam,]
# Partition data into train and test; test will be our oos data
set.seed(1)
df_split <- initial_split(df_sample, prop = 3/4)
df_train <- training(df_split)
df_test <- testing(df_split)

Exploratory Data Analysis

Univariate EDA

We observe that the univariate distributions of the continuous variables are all multi-modal and non-normal, but they are all normalised to the range of \([0, 1]\).

# flatten df into using pivot_longer and plot distribution
df %>% pivot_longer(cols = starts_with("cont"), names_to  = "cont") %>% 
   ggplot(aes(x = value))+
   geom_histogram(bins = 100, alpha = 0.85)+
   ggtitle("Continuous features distribution")+
   facet_wrap(cont~.,scales = "free") +
   theme_minimal()

From the distributions of categorical variables, we see that there are variables with substantially more observations in one category, and also variables with a high number of (\(>50\)) categories, which will be an issue to address in our preprocessing step.

# flatten df into using pivot_longer and plot distribution
df %>% pivot_longer(cols = contains(c("cat", "target")), names_to  = "cat") %>% 
   ggplot(aes(x = value))+
   geom_bar(alpha = 0.85)+
   ggtitle("Categorical features distribution")+
   facet_wrap(cat~.,scales = "free", ncol = 4) +
   theme_minimal(base_size = 30)

Bivariate EDA

We group the continuous variables by the target and plot them as boxplots to check for any obvious differences discernible by eye. From the plots, claims with target == 1 have lower values of cont3 on average (median) than claims with target == 0, hence we would expect a negative relationship between cont3 and target. Claims with target=1 also have a higher median value of cont4 than claims with target == 0.

# flatten df into using pivot_longer
# group by target and plot distribution
df[, c(cont_feats, target_col)] %>% 
  pivot_longer(cols = starts_with("cont"), names_to  = "var", values_to="value") %>% 
  ggplot(aes(x=target,y=value), fill=factor(value)) + 
  geom_boxplot() + coord_flip() + facet_wrap(~var, scales="free_x")

From our conditional boxplots, we can identify potential outliers. In particular we can spot many potential outliers for cont0, cont5, cont7, cont8, cont9 and cont10. To investigate this, we identified observations that lie at the extreme percentiles of these variables. Using the Hampel filter, which considers points lying outside the median plus or minus 3 mean absolute deviations as outliers, more than 200 observations per variable were classified as such. This suggests that these may not be outliers but that the distribution is just heavy-tailed. Without further information on the reasonable scale of values that individual variables can take (along with the fact that they are all normalised), we find it challenging to clearly identify outliers through descriptive statistics and decide not to exclude any such points using this approach. We will proceed to detect for outliers using a model approach in a subsequent section.

hampel_filter <- function(df){
   lower_bound <- median(df) - 3 * mad(df, constant = 1)
   upper_bound <- median(df) + 3 * mad(df, constant = 1)
   outlier_ind <- which(df < lower_bound | df > upper_bound)
   return(outlier_ind)
}
percentile_filter <- function(df, lq = 0.001, uq = 0.999){
   lower_bound <- quantile(df, lq)
   upper_bound <- quantile(df, uq)
   outlier_ind <- which(df < lower_bound | df > upper_bound)
   return(outlier_ind)
}
hampel_count <- function(x){length(hampel_filter(x))}
pct_count <- function(x){length(percentile_filter(x))}

outlier_counts <- df_train[, cont_feats] %>% map_dfr(hampel_count)
outlier_counts[2, ] <- df_train[, cont_feats] %>% map_dfr(pct_count)
outlier_counts

For categorical variables, we use stacked bar plots to show the percentages of observations in each category that correspond to target == 0 and target == 1 respectively. A much larger proportion of claims with cat13 == B appear to be associated with target == 1 compared to cat13 == A. On the other hand, a much larger percentage of claims correspond to target == 0 if cat18 is A or B, than if cat18 is C or D.

# flatten df into using pivot_longer
# group by target and plot distribution
df[, c(cat_feats, target_col)] %>% 
  pivot_longer(cols = starts_with("cat"), names_to  = "cat", values_to="value") %>% 
  ggplot(aes(x = value, fill=target)) + 
    geom_bar(position="fill") + 
    scale_y_continuous(name = "Within group Percentage", labels = scales::percent) +
    facet_wrap(~cat, scales="free_x", ncol = 4) +
    theme_minimal(base_size = 40)

We also inspect the correlation matrix for our continuous variables. There seems to be a cluster of variables - cont1, cont2, cont8 - that are highly correlated with each other. This could potentially lead to problems with multicollinearity when using linear models. In addition, we also consider the pearson correlation and our continuous variables, although not necessarily meaningful in this case given our target is binary, and in addition given the multi-modal distributions of the continuous variables we identified in our univariate exploratory data analysis. However, we note that the continuous variables have pearson correlations of roughly \([-0.2, 0.2]\), suggesting that there is some signal between the features and the target. Finally, we note that the pearson correlation only describes a linear and pairwise association between the variables; as such there could be complex non-linear associations and interactions between the variables as well.

cor_matrix <- cor(df[, cont_feats])
heatmap(cor_matrix, main="Correlation Matrix (Clustered)")

cor_with_target <- rownames_to_column(data.frame(cor(df[, c(cont_feats)], as.numeric(df$target))))
names(cor_with_target) <- c("feature", "pearson_corr")
cor_with_target %>%
  ggplot(aes(x=reorder(feature, -pearson_corr), y = pearson_corr)) + 
  geom_bar(stat='identity') + coord_flip() + ggtitle("Pearson Correlation of Continuous with Target")

We can use Principal Components Analysis (PCA) as a means to visualise the data in low-dimension, to determine if there are any explicitly discernible trends. By eye, the classes do not appear to be linearly separable - which suggest a non-linear method may be more effective. There do not appear to be any significant difference in the PCA representations for each class, although there are many observations with target == 1 closer to the bottom of the ellipsoid formed by the first two PCA loadings. We note that there is a connection between PCA and Ridge (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome 2009), and also that the first two principal components only capture about \(\approx 60\%\) variation in the continuous variables.

pcs <- prcomp(df[,cont_feats])
set.seed(2021)
data.frame(pc1=pcs$x[,1], pc2=pcs$x[,2], target=df[, "target"]) %>%
ggplot(aes(x = pc1, y = pc2, colour = target)) + 
  geom_jitter(alpha=0.7) + ggtitle('Principal Components')

# cumulative variance
cumul_var <- cumsum(pcs$sdev^2 / sum(pcs$sdev^2))
ggplot(data.frame(feature = 1:11, cumul_var = cumul_var)) + 
  geom_line(aes(x = feature,y = cumul_var)) + ggtitle("Cumulative Explained Variance Ratio") +
  scale_y_continuous(labels=percent)

Modelling

We first consider a naive model that always predicts a single label (in this case \(0\)) given it is the most frequently occurring class. In this case, the accuracy would \(1 - \hat{y} = 0.745\) This illustrates the issue with the accuracy metric - the naive accuracy is high due to the nature of the data, and hence subsequent model performances need to be compared with this benchmark.

We also consider the ROC-AUC metric (Receiving Operator Characteristic Area Under the Curve), and accuracy metric. Given the problem is one related to insurance, the modelling outcome of interest is not only to obtain the correct predictions (accuracy), but also accurate probabilities, which is what the AUC metric measures. AUC measures the performance of the classifier across all possible decision thresholds, which makes it more helpful to compare performance than the accuracy metric with default decision threshold set to 0.5. As we do not know the specific threshold relevant to the insurance context of the problem, we will report both accuracy and ROC for all models, and compare it to that of the baseline model in [section 1]. On the other hand, predicting all 0s would result in the lowest ROC-AUC score of 0.5 as expected.

# train-test
X_train = as.matrix(df_train[, cont_feats])
y_train = as.numeric(as.matrix(df_train$target))
X_test = as.matrix(df_test[, cont_feats])
y_test = as.numeric(as.matrix(df_test$target))

diagnosis <- function(train_pred, test_pred, train_true, test_true){
  train_classes <- ifelse(train_pred > 0.5, 1,0)
  test_classes <- ifelse(test_pred > 0.5, 1,0)
  acc1 <- mean(train_classes == train_true)
  auc1 <- auc(roc(train_true, train_pred, quiet=TRUE))
  acc2 <- mean(test_classes == test_true)
  auc2 <- auc(roc(test_true, test_pred, quiet=TRUE))
  data.frame(train_acc=acc1, train_auc=auc1, test_acc = acc2, test_auc=auc2)
}


results = data.frame(diagnosis(rep(0, dim(df_train)[1]), 
                               rep(0, dim(df_test)[1]), 
                               df_train$target, df_test$target),
                     row.names=c("naive"))
results

Logistic Regression (SGD)

To fulfill the project requirements, we demonstrate a `from scratch’ Stochastic Gradient Descent routine for Logistic Regression. The deriviation follows (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome 2009, 120–26)

The logistic loss is given by: \[l(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} y_{i} log(p(x_{i} ; \boldsymbol{\beta})) + (1 - y_{i}) log(1 - p(x_{i} ; \boldsymbol{\beta})) = \sum_{i = 1}^{N} \left [ y_{i}log \left (\frac{p(x_{i} ; \boldsymbol{\beta})}{1 - p(x_{i} ; \boldsymbol{\beta})} \right) + log(1 - p(x_{i} ; \boldsymbol{\beta})) \right ]\]

\[ l(\boldsymbol{\beta})= -\sum_{i = 1}^{N}\left [y_{i} \boldsymbol{\beta}^{T} x_{i} - log(1 + exp(\boldsymbol{\beta}^{T}x_{i})) \right ]\]

With the inclusion of a reularisation term, in this case a \(L^{2}\) penalty:

\[ l(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} \left [y_{i} \boldsymbol{\beta}^{T} x_{i} - log(1 + exp(\boldsymbol{\beta}^{T}x_{i})) \right ] - \lambda \boldsymbol{\beta}^{T} \boldsymbol{\beta}\]

The gradient of the loss function is given by:

\[\nabla(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} \left [ y_{i} x_{i} - \frac{x_{i}exp(\boldsymbol{\beta}^{T} x_{i})}{1 + exp(\boldsymbol{\beta}^{T} x_{i})} \right] - \lambda 2\boldsymbol{\beta}\]

We use the Barzilai-Borwein method (Murphy, Kevin P. 2012, 444–45) to determine the step size.

# binary crossentropy / log-loss
log_loss <- function(x, y, betas, lambda){
  logits <- x %*% betas
  - (t(y) %*% logits - sum(log(1 + exp(logits))) + lambda * t(betas) %*% betas) / dim(x)[1]
}
# logistic regression gradients
gradients <- function(x, y, betas, lambda){
  logits <- x %*% betas
  - (t(x) %*% (y - exp(logits)/(1 + exp(logits)))) - lambda *2 * betas / dim(x)[1]
}
p = dim(X_train)[2]
lambda = 0
n_iters <- 100
init_step_size <- 1e-6
set.seed(2021)
beta_init <- matrix(rnorm(p),nrow=p)
beta_path <- matrix(rep(0, n_iters * p), nrow = n_iters, ncol=p)
beta_path[1,] = beta_init
last_grad <- grad <- gradients(X_train, y_train, beta_path[1,], lambda)
beta_path[2,] = beta_init - init_step_size * grad
grad <- gradients(X_train, y_train, beta_path[2,], lambda)
losses <- rep(0, n_iters)
for (i in 3:n_iters){
    step_size <- as.numeric(t(beta_path[i - 1,] - beta_path[i - 2,]) %*% (grad - last_grad) / 
                    (t(grad - last_grad) %*% (grad - last_grad)))
    beta_path[i,] <- beta_path[i - 1,] - step_size * grad
    last_grad <- grad
    grad <- gradients(X_train, y_train, beta_path[i, ], lambda)
    losses[i] <- log_loss(X_train, y_train, beta_path[i,], lambda)
}
ggplot(data.frame(step = 3:n_iters, loss=losses[3:n_iters])) + 
  geom_line(aes(x = step, y = loss)) +
  ggtitle("Binary Crossentropy vs. Iterations")


pred_train <- as.numeric(1 / (1 + exp(-X_train %*% beta_path[100,])))
pred_test <- as.numeric(1 / (1 + exp(-X_test %*% beta_path[100,])))
results["sgd",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["sgd",]

Logistic Regression (Few Predictors)

As a baseline model, we build a simple logistic regression with a few predictors, which are selected from our exploratory data analysis to have discernible differences in target. These are cont3, cont4, cat13, cat18. We use the glm package to fit a logistic regression.

glm1 <- glm(target~cont3+cont4+cat13+cat18,data=df_train, family=binomial(link="logit"))
summary(glm1)

Call:
glm(formula = target ~ cont3 + cont4 + cat13 + cat18, family = binomial(link = "logit"), 
    data = df_train)

Deviance Residuals: 
    Min       1Q   Median       3Q      Max  
-1.5707  -0.6702  -0.6021   0.3931   2.0095  

Coefficients:
            Estimate Std. Error z value Pr(>|z|)    
(Intercept)  -1.4821     1.0756  -1.378  0.16824    
cont3        -0.6554     0.2276  -2.880  0.00398 ** 
cont4        -0.4772     0.2063  -2.313  0.02070 *  
cat13B        1.8681     0.3346   5.584 2.36e-08 ***
cat18B        0.5581     1.0714   0.521  0.60243    
cat18C        2.6081     1.0816   2.411  0.01590 *  
cat18D        2.4342     1.0805   2.253  0.02427 *  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 3406.6  on 2999  degrees of freedom
Residual deviance: 2962.8  on 2993  degrees of freedom
AIC: 2976.8

Number of Fisher Scoring iterations: 4

All four predictors are significant at 5% level, with the most significant predictors being… The coefficients of the dummy variables indicate the average difference between the log odds of that factor level group compared to the baseline level group. In our regression, the first category (A) of each categorical variable is taken as the baseline group. For example, the coefficient of cat13b implies the following equation: \[\text{logit} P(\text{target}=1|\text{cat13b} = 1) – \text{logit} P(\text{target}=0|\text{cat13b} = 1) = 1.8681. \] In words, this means that claims with cat13b = 1 have 33% higher log odds of target=1 than claims with \text{cat13b} == 0. However, we can only assert that there is some association - in this case it is statistically significant relationship with the p-value being 2.36e-08 - between the presence of the variable cat13b = 1 and the target being 1, but not whether there is a causation; in particular, given the lack of knowledge of what the variable represents, we cannot form any meaningful hypothesis.

To interpret the coefficients of the continuous variables, risk ratios need to be calculated using specific pairs of values of the predictors. The non-linearity of the logistic function means that a change of one unit in the value of a predictor is not the same across the range of the predictor.

pred_train <- predict(glm1, df_train, type="response")
pred_test <- predict(glm1, df_test, type="response")
results["glm-small",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-small",]

Logistic Regression (All Predictors)

We now run a logistic regression using all variables, using the glm package.

glm2 <- glm(target~., data=df_train, family=binomial(link="logit"), 
            control = list(maxit = 100))
# display(glm2)

pred_train <- predict(glm2, df_train, type="response")
glm2$xlevels = lapply(df[,cat_feats], levels)
pred_test <- predict(glm2, df_test, type="response")
results["glm-full",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-full",]
# anova(glm1, glm2, test="Chisq")

Outlier Detection

We attempt to detect outliers under a logistic regression. Formally, outliers are defined as observations with a response vector that is unusual conditional on covariates. They are formally identified through studentized residuals. Intuitively, outliers have large residuals and we can formally test (by looking at the Bonferroni–adjusted p-values) if these residuals are significantly larger than the other observations. We use the outlierTest function from the car to determine the outliers from the glm model.

Observations that are far from the average covariate pattern are considered to have high leverage and can be measured using the hat value. Here, there are many points with high leverage.

outlierTest(glm2)
outliers <- as.numeric(names(outlierTest(glm2)$p))

Finally, we measure for influence, which is an observation that is an outlier and have high leverage. These are likely to influence the regression coefficients and influence can be thought of as the product of leverage and outlier. Here, we plot studentised residuals against hat-values with the size of a circle being proportional to the Cook’s distance of an observation- a measure of influence.

influenceIndexPlot(glm2, vars = "hat")
influencePlot(glm2)

Here, we observe that there are a number of observations with high influence - outliers with high leverage. Thus, we remove these observations and compare the performance of our updated model with the original model.

In the later models, we will also exclude the same outliers.

influencers <- as.numeric(rownames(influencePlot(glm2)))
glm2_influencers <- update(glm2, subset = c(-influencers))
glm2_outliers <- update(glm2, subset = c(-outliers))
removal_list <- union(outliers, influencers)
glm2_removed <- update(glm2, subset = c(-removal_list))
compareCoefs(glm2, glm2_influencers, glm2_outliers, glm2_removed)
# actually just use glm2 and glm2_removed

Regularised Logistic Regression

Given the issue of high dimensionality, we consider a regularised form of logistic regression. We use the glmnet package; in doing so we need to convert the data type into matrices.The glmnet package requires the data to be in a matrix data type, and hence we make the corresponding adjustment.

X_train = df_train[, -length(df_train)]
y_train <- df_train$target
X_test = df_test[, -length(df_test)]
y_test <- df_test$target
X_train = model.matrix(~., X_train)
X_test = model.matrix(~., X_test)
glm3 <- cv.glmnet(X_train, y_train, 
                  family="binomial"(link="logit"), alpha=0)
glm3

Call:  cv.glmnet(x = X_train, y = y_train, family = binomial(link = "logit"),      alpha = 0) 

Measure: GLM Deviance 

    Lambda Index Measure      SE Nonzero
min 0.1422    80  0.7846 0.01822     458
1se 0.3606    70  0.8010 0.01636     458
pred_train <- as.numeric(predict(glm3, X_train, type="response"))
pred_test <- as.numeric(predict(glm3, X_test, type="response"))
results["glm-ridge",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-ridge",]

Random Forest

To improve performance, we draw on the usage of non-linear tree-based models, specifically Random Forests (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome 2009). Intuitively, a random forest averages different decision trees (known as bagging) so as to reduce the variance of individual trees. We use the

rf_recipe <- recipe(target~., data = df_train)

rf_model <- 
  rand_forest(trees=100) %>%
  set_engine("ranger", importance="impurity", seed=2021) %>%
  set_mode("classification")

rf_workflow <- workflow() %>%
  add_recipe(rf_recipe) %>%
  add_model(rf_model)

rf1 <- fit(rf_workflow, df_train)
ranger_obj <- pull_workflow_fit(rf1)$fit
# plot feature importances
rf_feat_imp <- rownames_to_column(data.frame(ranger_obj$variable.importance));
names(rf_feat_imp) <- c("feat", "importance")
ggplot(rf_feat_imp, aes(x = reorder(feat, importance), y = importance))+ 
      geom_bar(stat="identity", position="dodge")+ coord_flip()+
      ylab("Feature Importance (Gini Impurity)")+
      xlab("Feature")+
      ggtitle("Random Forest Feature Importances")
#evaluate metrics
pred_train <- unlist(predict(rf1,df_train,type='prob')[,2])
pred_test <- unlist(predict(rf1, df_test, type='prob')[,2])
results["rf",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["rf",]
temp <- function(x){partial(ranger_obj, train=df_train, pred.var = x, plot = TRUE, plot.engine = "ggplot2", paropts = list(.packages = "ranger"))}
plots <- lapply(names(df_train)[cont_feats], temp)
wrap_plots(plots)

The random forest has a test accuracy of 0.836 and a test AUC of 0.872, which is higher than the previous linear models. However, the train accuracy and AUC are significantly higher than the test performance, which suggest that there may be some degree of overfitting to the train data.

Random forests can be used to rank the importance of different features. Specifically, the x-axis is the Mean Decrease Accuracy, which reports how much accuracy the model loses when we exclude this variable. The more the accuracy falls by, the more important the particular variable is. Note here that for categorical variables, each level of the category is classified as a single variable. In this plot, we recorded the 30 most important variables.

We then run another random forest with the most important features. In doing so, we hope to reduce the degree of overfitting by reducing the complexity of the model. However, it does not make sense to drop some levels of a categorical variable while including the other levels. Hence, as long as a level is present in the top 30 features, we will include the entire category in our updated random forest model. This results in us keeping only 22 variables, from an initial 30.

Our reduced random forest has a slightly improved test accuracy and a slightly decreased test AUC. However, it does not solve the potential problem of overfitting as train performance is still significantly better than test performance. In fact, train performance on the reduced random forest is better than the random forest with a full set of variables - the reduced complexity of the model enabled it to have a lower bias on the training set.

XGBoost

For completeness, we also consider the xgboost library for gradient boosted decision trees. Gradient Boosted Decision Trees. The XGBoost package, introduced in (Chen, Tianqi and Guestrin, Carlos 2016) is a variant of Gradient Boosted Decision Trees (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome 2009, 353–74)

dmy_train <- dummyVars("~.", data = df_train[,-length(df_train)])
dmy_test <- dummyVars("~.", data = df_test[,-length(df_test)])
X_train <- as.matrix(data.frame(predict(dmy_train,df_train)))
X_test <- as.matrix(data.frame(predict(dmy_test,df_test)))
y_train = as.integer(as.matrix(df_train$target))
y_test = as.integer(as.matrix(df_test$target))
bst <- xgboost(data = X_train, label=y_train, max_depth = 2, nround = 10, 
               verbose=0,
               objective='binary:logistic',
               eval_metric="logloss")

pred_train <- predict(bst, X_train, type="response")
pred_test <- predict(bst, X_test, type="response")
results["xgb",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["xgb",]

importance_matrix <- xgb.importance(model=bst)
xgb.plot.importance(importance_matrix)

# shapley values  
xgboost::xgb.ggplot.shap.summary(X_test, model = bst, 
                                 target_class = 1, top_n = 20)  # Summary plot

CatBoost

We also consider briefly examine the catboost library for gradient boosted decision trees, given its popularity on machine learning competitions such as Kaggle. The CatBoost library has the advantage of learning a target encoding for categorical variables. From an implementation point of view, this may reduce the preprocessing that may be required.For details on CatBoost, refer to (Prokhorenkova, Liudmila and Gusev, Gleb and Vorobev, Aleksandr and Dorogush, Anna Veronika and Gulin, Andrey 2017)

X_train = df_train[,c(cat_feats, cont_feats)]
y_train = as.integer(df_train$target)
X_test = df_test[,c(cat_feats, cont_feats)]
y_test = as.integer(df_test$target)

pool <- catboost.load_pool(X_train, y_train, cat_features = cat_feats)
model <- catboost.train(pool, params=list(depth = 8, iterations = 10, 
                                          loss_function='Logloss', verbose=0))

pred_train <- catboost.predict(model, catboost.load_pool(X_train), prediction_type = 'Probability')
pred_test <- catboost.predict(model, catboost.load_pool(X_test), prediction_type = 'Probability')

# feature importance
feat_importance <- catboost.get_feature_importance(model, pool)
importances <- data.frame(feat_importance[order(feat_importance, decreasing=FALSE),])
importances$features = rownames(importances)
names(importances) <- c("importance","features")
importances$features <- factor(importances$features, level=importances$features)
ggplot(importances, aes(x=importance, y=features)) + 
  geom_bar(stat="identity") +
  ggtitle("CatBoost Feature Importance")


#Shapley Values
data_shap_tree <- catboost.get_feature_importance(model, pool = pool,
                                                  type = "ShapValues")
data_shap_tree <- data.frame(data_shap_tree[, -ncol(data_shap_tree)]) 
names(data_shap_tree) = names(df[, c(cat_feats, cont_feats)])

ggplot(stack(data_shap_tree), aes(x = ind, y = values)) +
    geom_point(aes(color = values)) + coord_flip() + 
    ggtitle("Shapley Values by variable")  + scale_color_viridis_c()


results["catboost",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["catboost",]

Results and Evaluation

results
results[order(-results$test_auc, -results$test_acc),]

Although the tree-based methods are less interpretable and more “black box” to some extent, we can make use of model interpretability techniques.

Bibliography

Chen, Tianqi and Guestrin, Carlos. 2016. “XGBoost: A Scalable Tree Boosting System.” https://arxiv.org/pdf/1603.02754.pdf.
Efron, Bradley and Hastie, Trevor. 2016. Computer Age Statistical Inference. Cambridge University Press.
Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer.
James, Gareth and Witten, Daniela and Hastie, Trevor and Robert Tibshirani. 2017. An Introduction To Statistical Learning. Springer.
Molnar, Christoph. 2019. Interpretable Machine Learning. “https://christophm.github.io/interpretable-ml-book”.
Murphy, Kevin P. 2012. Machine Learning: A Probabilistic Perspective. MIT Press. https://christophm.github.io/interpretable-ml-book.
Parr, Terence and Howard, Jeremy. 2019. The Mechanics of Machine Learning. https://mlbook.explained.ai/.
Prokhorenkova, Liudmila and Gusev, Gleb and Vorobev, Aleksandr and Dorogush, Anna Veronika and Gulin, Andrey. 2017. “CatBoost: Unbiased Boosting With Categorical Features.” https://arxiv.org/pdf/1706.09516.pdf.

Appendix

set.seed(2021)
cv_splits <- rsample::vfold_cv(df_train, strata = target, v= 3)
mod <- logistic_reg(penalty = tune(),
                    mixture = tune()) %>%
  set_engine("glmnet")

glmnet_recipe <- recipe(target~.,data = df_train) %>% 
  step_dummy(all_nominal(), -all_outcomes())

glmnet_workflow<- workflow() %>%
  add_recipe(glmnet_recipe) %>%
  add_model(mod)

glmn_set <- parameters(penalty(range = c(-5,1), trans = log10_trans()),
                       mixture())

glmn_grid <- 
  grid_regular(glmn_set, levels = c(7, 5))
ctrl <- control_grid(save_pred = TRUE, verbose = TRUE)

glmn_tune <- 
  tune_grid(glmnet_workflow,
            resamples = cv_splits,
            grid = glmn_grid,
            metrics = metric_set(roc_auc),
            control = ctrl)


best_glmn <- select_best(glmn_tune, metric = "roc_auc")

glmnet_model <- 
  logistic_reg() %>%
  set_engine("glmnet", seed=2021) %>%
  set_mode("classification")



glm3 <- fit(glmnet_workflow, data = df_train)
xgb_spec <- boost_tree(
  trees = 100, 
  tree_depth = tune(),
  learn_rate = tune()                         ## step size
) %>% 
  set_engine("xgboost") %>% 
  set_mode("classification")

xgb_grid <- grid_latin_hypercube(
  tree_depth(),
  learn_rate(),
  size = 5
)

xgb_wf <- workflow() %>%
  add_formula(target ~ .) %>%
  add_model(xgb_spec)

set.seed(123)
vb_folds <- vfold_cv(df_train, strata = target)

doParallel::registerDoParallel()

set.seed(234)
xgb_res <- tune_grid(
  xgb_wf,
  resamples = vb_folds,
  grid = xgb_grid,
  control = control_grid(save_pred = TRUE)
)
best_auc <- select_best(xgb_res, "roc_auc")
final_xgb <- finalize_workflow(
  xgb_wf,
  best_auc
)
library(vip)

final_xgb %>%
  fit(data = vb_train) %>%
  pull_workflow_fit() %>%
  vip(geom = "point")

final_res <- last_fit(final_xgb, df_split)

collect_metrics(final_res)
xgb_res %>%
  collect_metrics() %>%
  filter(.metric == "roc_auc") %>%
  select(mean, mtry:sample_size) %>%
  pivot_longer(mtry:sample_size,
               values_to = "value",
               names_to = "parameter"
  ) %>%
  ggplot(aes(value, mean, color = parameter)) +
  geom_point(alpha = 0.8, show.legend = FALSE) +
  facet_wrap(~parameter, scales = "free_x") +
  labs(x = NULL, y = "AUC")
"https://curso-r.github.io/treesnip/index.html"
library(treesnip)
LS0tCnRpdGxlOiAiU1QzMTAgQ291cnNlIFByb2plY3QiCmF1dGhvcjogIkNocmlzIENoaWEsIE11biBGYWkgQ2hhbiwgWmhlbiBZZW4gQ2hhbiIKZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJWQvJW0vJXknKWAiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIGRmX3ByaW50OiBwYWdlZAogICAga2VlcF9tZDogdHJ1ZQogIHBkZl9kb2N1bWVudDogZGVmYXVsdApoZWFkZXItaW5jbHVkZXM6Ci0gXHVzZXBhY2thZ2Uge2h5cGVycmVmfQotIFxoeXBlcnNldHVwIHtjb2xvcmxpbmtzID0gdHJ1ZSwgbGlua2NvbG9yID0gYmx1ZSwgdXJsY29sb3IgPSBibHVlfQpyZWZlcmVuY2VzOgotIGlkOiBoYXN0aWUyMDA5ZWxlbWVudHMKICB0aXRsZTogJ1RoZSBFbGVtZW50cyBvZiBTdGF0aXN0aWNhbCBMZWFybmluZzogRGF0YSBNaW5pbmcsIEluZmVyZW5jZSwgYW5kIFByZWRpY3Rpb24nCiAgYXV0aG9yOiAiSGFzdGllLCBUcmV2b3IgYW5kIFRpYnNoaXJhbmksIFJvYmVydCBhbmQgRnJpZWRtYW4sIEplcm9tZSIKICBwdWJsaXNoZXI6IFNwcmluZ2VyCiAgdHlwZTogYm9vawogIGlzc3VlZDoKICAgIHllYXI6IDIwMDkKLSBpZDogamFtZXMyMDE3aW50cm9kdWN0aW9uCiAgdGl0bGU6ICJBbiBJbnRyb2R1Y3Rpb24gVG8gU3RhdGlzdGljYWwgTGVhcm5pbmciCiAgYXV0aG9yOiAiSmFtZXMsIEdhcmV0aCBhbmQgV2l0dGVuLCBEYW5pZWxhIGFuZCBIYXN0aWUsIFRyZXZvciBhbmQgUm9iZXJ0IFRpYnNoaXJhbmkiCiAgcHVibGlzaGVyOiBTcHJpbmdlcgogIHR5cGU6IGJvb2sKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE3Ci0gaWQ6IGVmcm9uMjAxNmNvbXB1dGVyCiAgdGl0bGU6ICJDb21wdXRlciBBZ2UgU3RhdGlzdGljYWwgSW5mZXJlbmNlIgogIGF1dGhvcjogIkVmcm9uLCBCcmFkbGV5IGFuZCBIYXN0aWUsIFRyZXZvciIKICBwdWJsaXNoZXI6IENhbWJyaWRnZSBVbml2ZXJzaXR5IFByZXNzCiAgdHlwZTogYm9vawogIGlzc3VlZDoKICAgIHllYXI6IDIwMTYKLSBpZDogbW9sbmFyMjAxOQogIHRpdGxlOiAiSW50ZXJwcmV0YWJsZSBNYWNoaW5lIExlYXJuaW5nIgogIGF1dGhvcjogIk1vbG5hciwgQ2hyaXN0b3BoIgogIHR5cGU6IGJvb2sKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE5CiAgVVJMOiDigJxodHRwczovL2NocmlzdG9waG0uZ2l0aHViLmlvL2ludGVycHJldGFibGUtbWwtYm9va+KAnQotIGlkOiBtdXJwaHkyMDEybWFjaGluZQogIHRpdGxlOiAiTWFjaGluZSBMZWFybmluZzogQSBQcm9iYWJpbGlzdGljIFBlcnNwZWN0aXZlIgogIGF1dGhvcjogIk11cnBoeSwgS2V2aW4gUC4iCiAgcHVibGlzaGVyOiBNSVQgUHJlc3MKICB0eXBlOiBib29rCiAgaXNzdWVkOgogICAgeWVhcjogMjAxMgogIFVSTDogImh0dHBzOi8vY2hyaXN0b3BobS5naXRodWIuaW8vaW50ZXJwcmV0YWJsZS1tbC1ib29rIgotIGlkOiBwcm9raG9yZW5rb3ZhMjAxN2NhdGJvb3N0CiAgdGl0bGU6ICJDYXRCb29zdDogVW5iaWFzZWQgQm9vc3RpbmcgV2l0aCBDYXRlZ29yaWNhbCBGZWF0dXJlcyIKICB0eXBlOiBhcnRpY2xlLWpvdXJuYWwKICBhdXRob3I6ICJQcm9raG9yZW5rb3ZhLCBMaXVkbWlsYSBhbmQgR3VzZXYsIEdsZWIgYW5kIFZvcm9iZXYsIEFsZWtzYW5kciBhbmQgRG9yb2d1c2gsIEFubmEgVmVyb25pa2EgYW5kIEd1bGluLCBBbmRyZXkiCiAgaXNzdWVkOgogICAgeWVhcjogMjAxNwogIFVSTDogImh0dHBzOi8vYXJ4aXYub3JnL3BkZi8xNzA2LjA5NTE2LnBkZiIKLSBpZDogY2hlbjIwMTZ4Z2Jvb3N0CiAgdGl0bGU6ICJYR0Jvb3N0OiBBIFNjYWxhYmxlIFRyZWUgQm9vc3RpbmcgU3lzdGVtIgogIGF1dGhvcjogIkNoZW4sIFRpYW5xaSBhbmQgR3Vlc3RyaW4sIENhcmxvcyIKICB0eXBlOiBhcnRpY2xlLWpvdXJuYWwKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE2CiAgVVJMOiAiaHR0cHM6Ly9hcnhpdi5vcmcvcGRmLzE2MDMuMDI3NTQucGRmIgotIGlkOiBwYXJyMjAxOW1vbWwKICB0aXRsZTogIlRoZSBNZWNoYW5pY3Mgb2YgTWFjaGluZSBMZWFybmluZyIKICBhdXRob3I6ICJQYXJyLCBUZXJlbmNlIGFuZCBIb3dhcmQsIEplcmVteSIKICB0eXBlOiBib29rCiAgaXNzdWVkOgogICAgeWVhcjogMjAxOQogIFVSTDogImh0dHBzOi8vbWxib29rLmV4cGxhaW5lZC5haS8iCi0tLQoKIyBTVDMxMCBDb3Vyc2UgUHJvamVjdAoKVGhlIGFpbSBvZiB0aGlzIHByb2plY3QgaXMgdG8gZGVtb25zdHJhdGUgdGhlIHVzZSBvZiBtYWNoaW5lIGxlYXJuaW5nIHRlY2huaXF1ZXMgbGVhcm50IGluIHRoZSBTVDMxMCBNYWNoaW5lIExlYXJuaW5nIG1vZHVsZS4gV2UgcmVseSBvbiBib3RoIGxpbmVhciAoTG9naXN0aWMgUmVncmVzc2lvbikgYW5kIG5vbi1saW5lYXIgbWV0aG9kcyAoUmFuZG9tIEZvcmVzdHMgYW5kIEdyYWRpZW50IEJvb3N0ZWQgRGVjaXNpb24gVHJlZXMpIGZvciBhIGNsYXNzaWZpY2F0aW9uIHByb2JsZW0uCgoqKlJlbWFyayoqOiBJZiBleGVjdXRpbmcgdGhpcyBub3RlYm9va3MgYXMgYSBgLlJtZGAgZmlsZSwgZW5zdXJlIHRoYXQgYWxsIGxpYnJhcmllcyBhbmQgZGVwZW5kZW5jaWVzIGFyZSBpbnN0YWxsZWQgYW5kIHRoYXQgdGhlIGNodW5rcyBhcmUgZXhlY3V0ZWQgaW4gc2VxdWVudGlhbCBvcmRlci4KCiMjIERhdGFzZXQKCldlIGhhdmUgb2J0YWluZWQgZGF0YSBmcm9tIHRoZSBbS2FnZ2xlIE1hcmNoIFRhYnVsYXIgUGxheWdyb3VuZF0oI2h0dHBzOi8vd3d3LmthZ2dsZS5jb20vYy90YWJ1bGFyLXBsYXlncm91bmQtc2VyaWVzLW1hci0yMDIxL292ZXJ2aWV3KSBjb21wZXRpdGlvbi4gVGhlIGRhdGEgY29uc2lzdHMgb2YgKmFub255bWlzZWQgZmVhdHVyZXMqLCB3aGljaCBjb3JyZXNwb25kIHRvIGEgYmluYXJ5IG91dGNvbWUgdmFyaWFibGU7IGluIG90aGVyIHdvcmRzIHRoZSB0YXNrIGlzIGEgKipjbGFzc2lmaWNhdGlvbiBwcm9ibGVtKiouIEFsdGhvdWdoIHRoZSBkYXRhIGlzIGFub255bWlzZWQsIHRoZSBjaGFsbGVuZ2UgZGVzY3JpcHRpb24gc3RhdGVzOgoKPiBUaGUgZGF0YXNldCBpcyB1c2VkIGZvciB0aGlzIGNvbXBldGl0aW9uIGlzIHN5bnRoZXRpYyBidXQgYmFzZWQgb24gYSByZWFsIGRhdGFzZXQgYW5kIGdlbmVyYXRlZCB1c2luZyBhIENUR0FOLiBUaGUgb3JpZ2luYWwgZGF0YXNldCBkZWFscyB3aXRoIHByZWRpY3RpbmcgdGhlIGFtb3VudCBvZiBhbiBpbnN1cmFuY2UgY2xhaW0uIEFsdGhvdWdoIHRoZSBmZWF0dXJlcyBhcmUgYW5vbnltaXplZCwgdGhleSBoYXZlIHByb3BlcnRpZXMgcmVsYXRpbmcgdG8gcmVhbC13b3JsZCBmZWF0dXJlcy4KClRoZSBkYXRhc2V0IGNvbnNpc3RzIG9mIDMwIGZlYXR1cmVzLCAgMTkgKmNhdGVnb3JpY2FsIHZhcmlhYmxlcyogYW5kIDExIG51bWVyaWNhbCB2YXJpYWJsZXMuLCBhbmQgYSBiaW5hcnkgb3V0Y29tZSB2YXJpYWJsZSBgdGFyZ2V0YC4gNzMuNSUgb2YgdGhlIG9ic2VydmF0aW9ucyBoYXZlIOKAmHRhcmdldD09MeKAmSwgc3VnZ2VzdGluZyBhbiAqaW1iYWxhbmNlZCBkYXRhc2V0Ki4gV2Ugd2lsbCBuZWVkIHRvIHByb2Nlc3MgdGhlc2UgY2F0ZWdvcmljYWwgdmFyaWFibGVzIGluIHNvbWUgbWFubmVyLCB3aGljaCB3ZSBzaGFsbCBjb25zaWRlciBpbiBbc3Vic2VxdWVudCBzZWN0aW9uc10oI3ByZXByb2Nlc3NpbmcpLgoKCgpgYGB7ciBsb2FkLWxpYnMsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkocGF0Y2h3b3JrKQpsaWJyYXJ5KGJyb29tKQpsaWJyYXJ5KHRpZHltb2RlbHMpCmxpYnJhcnkoYXJtKQpsaWJyYXJ5KGNhcikgI291dGxpZXIKbGlicmFyeSh0aWR5cikKbGlicmFyeShnbG1uZXQpCmxpYnJhcnkoY2FyZXQpCmxpYnJhcnkocmFuZG9tRm9yZXN0KQpsaWJyYXJ5KHhnYm9vc3QpCmxpYnJhcnkoY2F0Ym9vc3QpCmxpYnJhcnkoZTEwNzEpCmxpYnJhcnkoZGF0YS50YWJsZSkKbGlicmFyeShkb1BhcmFsbGVsKQpsaWJyYXJ5KGZvcmVhY2gpCmxpYnJhcnkocFJPQykKbGlicmFyeShwZHApCmRmIDwtIHJlYWQuY3N2KGZpbGUgPSAiLi4vZGF0YS90cmFpbi5jc3YiKQpjYXQoYygiVGhlIGRpbWVuc2lvbnMgb2YgdGhlIGFycmF5IGFyZSA6IiwgZGltKGRmKVsxXSwgIiwgIiwgZGltKGRmKVsyXSkpCmBgYApUaGUgZGF0YXNldCBjb25zaXN0cyBvZiAzMCBmZWF0dXJlcywgIDE5ICpjYXRlZ29yaWNhbCB2YXJpYWJsZXMqIGFuZCAxMSBudW1lcmljYWwgdmFyaWFibGVzLiwgYW5kIGEgYmluYXJ5IG91dGNvbWUgdmFyaWFibGUgYHRhcmdldGAuIFdlIHdpbGwgbmVlZCB0byBwcm9jZXNzIHRoZXNlIGNhdGVnb3JpY2FsIHZhcmlhYmxlcyBpbiBzb21lIG1hbm5lciwgd2hpY2ggd2Ugc2hhbGwgY29uc2lkZXIgaW4gdGhlIFtzdWJzZXF1ZW50IHNlY3Rpb25dKCNwcmVwcm9jZXNzaW5nKS4KCkEgY2hhbGxlbmdlIGlzIHRoYXQgd2UgaGF2ZSBubyAqc3BlY2lmaWMqIGRvbWFpbiBrbm93bGVkZ2UgYWJvdXQgdGhlIG1lYW5pbmcgb2YgcGFydGljdWxhciBmZWF0dXJlcywgYW5kIHdoZXRoZXIgdGhleSBtYXkgYmUgdXNlZnVsLiBOb25ldGhlbGVzcywgd2UgY2FuIHJlc29ydCB0byBtb2RlbCBpbnRlcnByZXRhYmlsaXR5IG1ldGhvZHMgW0Btb2xuYXIyMDE5XSB0byBvYnRhaW4gYW4gZXgtcG9zdCBleHBsYW5hdGlvbiBvZiBvdXIgbW9kZWxzLiBJbiB0aGUgbGluZWFyIGNhc2UsIHdlIGNhbiBleGFtaW5lIGNvZWZmaWNpZW50cyBhbmQgdGhlaXIgc3RhdGlzdGljYWwgc2lnbmlmaWNhbmNlLCBhbmQgaW4gdGhlIGNhc2Ugb2YgdHJlZS1iYXNlZCBtb2RlbHMsIHdlIGNhbiB1dGlsaXNlIGZlYXR1cmUgaW1wb3J0YW5jZXMsIHBhcnRpYWwgZGVwZW5kZW5jZSBwbG90cywgYW5kIFNoYXBsZXkgVmFsdWVzLgoKIyMgUHJlcHJvY2Vzc2luZwpXZSBmaXJzdCByZW1vdmUgdGhlIGZpcnN0IGNvbHVtbiBgaWRgLCB3aGljaCByZXByZXNlbnRzIGFuIHVuaXF1ZSBpZGVudGlmaWVyIGZvciBlYWNoIG9ic2VydmF0aW9uLiBXZSB0aGVuIGNvbnZlcnQgdGhlIGZpcnN0IDE5IGNvbHVtbnMsIHdoaWNoIGFyZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgaW50byB0aGUgKmZhY3RvciogZGF0YSB0eXBlIGluIFIsIFRvIHJlZHVjZSBjb21wdXRhdGlvbmFsIHRpbWUsIHdlIHN1YnNhbXBsZSA0MDAwIG9ic2VydmF0aW9ucyBmcm9tIHRoZSBjb21wbGV0ZSBkYXRhc2V0IG9mIDMwMCwwMDAgb2JzZXJ2YXRpb25zLiBGb3Igb3VyIHN1YnNlcXVlbnQgYW5hbHlzaXMsIHdlIHdpbGwgdXNlIG9ubHkgdGhpcyBzdWJzYW1wbGUgb2YgNDAwMCBvYnNlcnZhdGlvbnMsIGFsdGhvdWdoIHRoZSBhcHByb2FjaGVzIGNhbiBiZSBleHRlbmRlZCB0byBhIGxhcmdlciBkYXRhc2V0IGdpdmVuIGdyZWF0ZXIgY29tcHV0YXRpb25hbCByZXNvdXJjZXMuICBXZSBmdXJ0aGVyIHBhcnRpdGlvbiB0aGUgNDAwMCBvYnNlcnZhdGlvbnMsIGludG8gYSB0cmFpbiBzZXQgb2YgMzAwMCBvYnNlcnZhdGlvbnMgYW5kIGEgdGVzdCBzZXQgb2YgIDEwMDAgb2JzZXJ2YXRpb25zLiBBbGwgdHJhaW5pbmcgYW5kIHR1bmluZyBhcmUgcGVyZm9ybWVkIG9uIHRoZSB0cmFpbmluZyBkYXRhLCBhbmQgd2Ugd2lsbCBjb25zaWRlciBtb2RlbCBwZXJmb3JtYW5jZSBvbiB0aGUgdGVzdCBzZXQgcGVyZm9ybWFuY2Ugc2NvcmVzLgoKKipSZW1hcmsqKjogRGlmZmVyZW50IG1vZGVscyB3b3VsZCByZXF1aXJlIGRpZmZlcmVudCBwcmVwcm9jZXNzaW5nIGZvciB0aGUgY2F0ZWdvcmljYWwgdmFyaWFibGVzLCBhbmQgdGh1cyB3ZSB3aWxsIGZ1cnRoZXIgYWRkcmVzcyBpbiBzdWJzZXF1ZW50IHNlY3Rpb25zOyBmb3IgZXhhbXBsZSB0aGUgYGdsbWAgcGFja2FnZSBjYW4gYWNjZXB0ICpmYWN0b3JzKiBhcyBhIGRhdGEgdHlwZSwgd2hlcmVhcyBmb3IgYGdsbW5ldGAgdGhleSBtdXN0IGJlIGNvbnZlcnRlZCB0byB0aGUgbW9kZWwubWF0cml4IGZvcm1hdC4KCioqUmVtYXJrKio6IFdoZW4gZW5jb2RpbmcgdGhlIGNhdGVnb3JpY2FsIHZhcmlhYmxlcyBhcyBkdW1teSB2YXJpYWJsZXMgaW4gb3VyIHN1YnNlcXVlbnQgYW5hbHlzaXMsIHdlIGZpbmQgdGhhdCB0aGVyZSBhcmUgb3ZlciA2MDAgdW5pcXVlIGNhdGVnb3JpZXMgYWNyb3NzIGFsbCAxOSBvZiB0aGUgY2F0ZWdvcmljYWwgdmFyaWFibGVzLiAgV2UgY291bGQgYWxzbyBjb25zaWRlciBkaWZmZXJlbnQgbWV0aG9kcyB0byBwcm9jZXNzIGNhdGVnb3JpY2FsIHZhcmlhYmxlcywgc3VjaCBhcyBtZXJnaW5nIGxlc3MgZnJlcXVlbnRseSBvY2N1cmluZyBjYXRlZ29yaWVzLCBvciAgKnRhcmdldCBlbmNvZGluZyogW0BwYXJyMjAxOW1vbWwsIGNoLiA2XS4gTm9uZXRoZWxlc3MsIHdlIHN0aWNrIHdpdGggdGhlIGZhY3RvcnMgYW5kIGR1bW1pZXMgYXBwcm9hY2ggZ2l2ZW4gb3VyIGxhY2sgb2YgZmFtaWxpYXJpdHkgd2l0aCB0aGVzZSBvdGhlciBtZXRob2RzLgoKCgpgYGB7ciBwYXJ0aXRpb259CmNhdF9mZWF0cyA9IDE6MTkgIyB0aGUgZmlyc3QgMTkgY29sdW1ucyBhcmUgY2F0ZWdvcmljYWwgCmNvbnRfZmVhdHMgPC0gMjA6MzAgIyBhbmQgdGhlIG5leHQgMTEgYXJlIGNvbnRpbnVvdXMKdGFyZ2V0X2NvbCA8LSAzMSAjIHRhcmdldAojIGNvbnZlcnQgY2F0cyB0byBmYWN0b3JzCmRmIDwtIGNvbHVtbl90b19yb3duYW1lcyhkZiwgdmFyID0gImlkIikgJT4lIAogICAgICAgICBtdXRhdGVfaWYoaXMuY2hhcmFjdGVyLGFzLmZhY3RvcikgJT4lIAogICAgICAgICBtdXRhdGVfYXQodmFycyh0YXJnZXQpLCBmYWN0b3IpCiMgc3Vic2FtcGxlIHRoZSBkYXRhIGZvciBmYXN0ZXIgbW9kZWwgaW1wdXRhdGlvbgpzZXQuc2VlZCgxKQpzYW0gPSBzYW1wbGUoMTpucm93KGRmKSwgNDAwMCkKZGZfc2FtcGxlID0gZGZbc2FtLF0KIyBQYXJ0aXRpb24gZGF0YSBpbnRvIHRyYWluIGFuZCB0ZXN0OyB0ZXN0IHdpbGwgYmUgb3VyIG9vcyBkYXRhCnNldC5zZWVkKDEpCmRmX3NwbGl0IDwtIGluaXRpYWxfc3BsaXQoZGZfc2FtcGxlLCBwcm9wID0gMy80KQpkZl90cmFpbiA8LSB0cmFpbmluZyhkZl9zcGxpdCkKZGZfdGVzdCA8LSB0ZXN0aW5nKGRmX3NwbGl0KQpgYGAKCiMjIEV4cGxvcmF0b3J5IERhdGEgQW5hbHlzaXMKCiMjIyBVbml2YXJpYXRlIEVEQQpXZSBvYnNlcnZlIHRoYXQgdGhlIHVuaXZhcmlhdGUgZGlzdHJpYnV0aW9ucyBvZiB0aGUgKmNvbnRpbnVvdXMqIHZhcmlhYmxlcyBhcmUgYWxsIG11bHRpLW1vZGFsIGFuZCBub24tbm9ybWFsLCBidXQgdGhleSBhcmUgYWxsIG5vcm1hbGlzZWQgdG8gdGhlIHJhbmdlIG9mICRbMCwgMV0kLgpgYGB7ciBjb250LXZpen0KIyBmbGF0dGVuIGRmIGludG8gdXNpbmcgcGl2b3RfbG9uZ2VyIGFuZCBwbG90IGRpc3RyaWJ1dGlvbgpkZiAlPiUgcGl2b3RfbG9uZ2VyKGNvbHMgPSBzdGFydHNfd2l0aCgiY29udCIpLCBuYW1lc190byAgPSAiY29udCIpICU+JSAKICAgZ2dwbG90KGFlcyh4ID0gdmFsdWUpKSsKICAgZ2VvbV9oaXN0b2dyYW0oYmlucyA9IDEwMCwgYWxwaGEgPSAwLjg1KSsKICAgZ2d0aXRsZSgiQ29udGludW91cyBmZWF0dXJlcyBkaXN0cmlidXRpb24iKSsKICAgZmFjZXRfd3JhcChjb250fi4sc2NhbGVzID0gImZyZWUiKSArCiAgIHRoZW1lX21pbmltYWwoKQpgYGAKRnJvbSB0aGUgZGlzdHJpYnV0aW9ucyBvZiBjYXRlZ29yaWNhbCB2YXJpYWJsZXMsIHdlIHNlZSB0aGF0IHRoZXJlIGFyZSB2YXJpYWJsZXMgd2l0aCBzdWJzdGFudGlhbGx5IG1vcmUgb2JzZXJ2YXRpb25zIGluIG9uZSBjYXRlZ29yeSwgYW5kIGFsc28gdmFyaWFibGVzIHdpdGggYSBoaWdoIG51bWJlciBvZiAoJD41MCQpIGNhdGVnb3JpZXMsIHdoaWNoIHdpbGwgYmUgYW4gaXNzdWUgdG8gYWRkcmVzcyBpbiBvdXIgcHJlcHJvY2Vzc2luZyBzdGVwLiAgCmBgYHtyIGNhdC12aXosIGZpZy53aWR0aD0xNSwgZmlnLmhlaWdodD0xNX0KIyBmbGF0dGVuIGRmIGludG8gdXNpbmcgcGl2b3RfbG9uZ2VyIGFuZCBwbG90IGRpc3RyaWJ1dGlvbgpkZiAlPiUgcGl2b3RfbG9uZ2VyKGNvbHMgPSBjb250YWlucyhjKCJjYXQiLCAidGFyZ2V0IikpLCBuYW1lc190byAgPSAiY2F0IikgJT4lIAogICBnZ3Bsb3QoYWVzKHggPSB2YWx1ZSkpKwogICBnZW9tX2JhcihhbHBoYSA9IDAuODUpKwogICBnZ3RpdGxlKCJDYXRlZ29yaWNhbCBmZWF0dXJlcyBkaXN0cmlidXRpb24iKSsKICAgZmFjZXRfd3JhcChjYXR+LixzY2FsZXMgPSAiZnJlZSIsIG5jb2wgPSA0KSArCiAgIHRoZW1lX21pbmltYWwoYmFzZV9zaXplID0gMzApCmBgYAoKCgojIyMgQml2YXJpYXRlIEVEQQoKV2UgZ3JvdXAgdGhlIGNvbnRpbnVvdXMgdmFyaWFibGVzIGJ5IHRoZSB0YXJnZXQgYW5kIHBsb3QgdGhlbSBhcyBib3hwbG90cyB0byBjaGVjayBmb3IgYW55IG9idmlvdXMgZGlmZmVyZW5jZXMgZGlzY2VybmlibGUgYnkgZXllLiBGcm9tIHRoZSBwbG90cywgY2xhaW1zIHdpdGggYHRhcmdldCA9PSAxYCBoYXZlIGxvd2VyIHZhbHVlcyBvZiBjb250MyBvbiBhdmVyYWdlIChtZWRpYW4pIHRoYW4gY2xhaW1zIHdpdGggYHRhcmdldCA9PSAwYCwgaGVuY2Ugd2Ugd291bGQgZXhwZWN0IGEgbmVnYXRpdmUgcmVsYXRpb25zaGlwIGJldHdlZW4gY29udDMgYW5kIHRhcmdldC4gQ2xhaW1zIHdpdGggdGFyZ2V0PTEgYWxzbyBoYXZlIGEgaGlnaGVyIG1lZGlhbiB2YWx1ZSBvZiBjb250NCB0aGFuIGNsYWltcyB3aXRoIGB0YXJnZXQgPT0gMGAuCgpgYGB7ciBjb250LWJ5LXRhcmdldH0KIyBmbGF0dGVuIGRmIGludG8gdXNpbmcgcGl2b3RfbG9uZ2VyCiMgZ3JvdXAgYnkgdGFyZ2V0IGFuZCBwbG90IGRpc3RyaWJ1dGlvbgpkZlssIGMoY29udF9mZWF0cywgdGFyZ2V0X2NvbCldICU+JSAKICBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJjb250IiksIG5hbWVzX3RvICA9ICJ2YXIiLCB2YWx1ZXNfdG89InZhbHVlIikgJT4lIAogIGdncGxvdChhZXMoeD10YXJnZXQseT12YWx1ZSksIGZpbGw9ZmFjdG9yKHZhbHVlKSkgKyAKICBnZW9tX2JveHBsb3QoKSArIGNvb3JkX2ZsaXAoKSArIGZhY2V0X3dyYXAofnZhciwgc2NhbGVzPSJmcmVlX3giKQpgYGAKCkZyb20gb3VyIGNvbmRpdGlvbmFsIGJveHBsb3RzLCB3ZSBjYW4gaWRlbnRpZnkgcG90ZW50aWFsIG91dGxpZXJzLiBJbiBwYXJ0aWN1bGFyIHdlIGNhbiBzcG90IG1hbnkgcG90ZW50aWFsIG91dGxpZXJzIGZvciBgY29udDAsIGNvbnQ1LCBjb250NywgY29udDgsIGNvbnQ5IGFuZCBjb250MTBgLiBUbyBpbnZlc3RpZ2F0ZSB0aGlzLCB3ZSBpZGVudGlmaWVkIG9ic2VydmF0aW9ucyB0aGF0IGxpZSBhdCB0aGUgZXh0cmVtZSBwZXJjZW50aWxlcyBvZiB0aGVzZSB2YXJpYWJsZXMuIFVzaW5nIHRoZSBIYW1wZWwgZmlsdGVyLCB3aGljaCBjb25zaWRlcnMgcG9pbnRzIGx5aW5nIG91dHNpZGUgdGhlIG1lZGlhbiBwbHVzIG9yIG1pbnVzIDMgbWVhbiBhYnNvbHV0ZSBkZXZpYXRpb25zIGFzIG91dGxpZXJzLCBtb3JlIHRoYW4gMjAwIG9ic2VydmF0aW9ucyBwZXIgdmFyaWFibGUgd2VyZSBjbGFzc2lmaWVkIGFzIHN1Y2guIFRoaXMgc3VnZ2VzdHMgdGhhdCB0aGVzZSBtYXkgbm90IGJlIG91dGxpZXJzIGJ1dCB0aGF0IHRoZSBkaXN0cmlidXRpb24gaXMganVzdCBoZWF2eS10YWlsZWQuIFdpdGhvdXQgZnVydGhlciBpbmZvcm1hdGlvbiBvbiB0aGUgcmVhc29uYWJsZSBzY2FsZSBvZiB2YWx1ZXMgdGhhdCBpbmRpdmlkdWFsIHZhcmlhYmxlcyBjYW4gdGFrZSAoYWxvbmcgd2l0aCB0aGUgZmFjdCB0aGF0IHRoZXkgYXJlIGFsbCBub3JtYWxpc2VkKSwgd2UgZmluZCBpdCBjaGFsbGVuZ2luZyB0byBjbGVhcmx5IGlkZW50aWZ5IG91dGxpZXJzIHRocm91Z2ggZGVzY3JpcHRpdmUgc3RhdGlzdGljcyBhbmQgZGVjaWRlIG5vdCB0byBleGNsdWRlIGFueSBzdWNoIHBvaW50cyB1c2luZyB0aGlzIGFwcHJvYWNoLiBXZSB3aWxsIHByb2NlZWQgdG8gZGV0ZWN0IGZvciBvdXRsaWVycyB1c2luZyBhIG1vZGVsIGFwcHJvYWNoIGluIGEgc3Vic2VxdWVudCBzZWN0aW9uLiAKCgpgYGB7cn0KaGFtcGVsX2ZpbHRlciA8LSBmdW5jdGlvbihkZil7CiAgIGxvd2VyX2JvdW5kIDwtIG1lZGlhbihkZikgLSAzICogbWFkKGRmLCBjb25zdGFudCA9IDEpCiAgIHVwcGVyX2JvdW5kIDwtIG1lZGlhbihkZikgKyAzICogbWFkKGRmLCBjb25zdGFudCA9IDEpCiAgIG91dGxpZXJfaW5kIDwtIHdoaWNoKGRmIDwgbG93ZXJfYm91bmQgfCBkZiA+IHVwcGVyX2JvdW5kKQogICByZXR1cm4ob3V0bGllcl9pbmQpCn0KcGVyY2VudGlsZV9maWx0ZXIgPC0gZnVuY3Rpb24oZGYsIGxxID0gMC4wMDEsIHVxID0gMC45OTkpewogICBsb3dlcl9ib3VuZCA8LSBxdWFudGlsZShkZiwgbHEpCiAgIHVwcGVyX2JvdW5kIDwtIHF1YW50aWxlKGRmLCB1cSkKICAgb3V0bGllcl9pbmQgPC0gd2hpY2goZGYgPCBsb3dlcl9ib3VuZCB8IGRmID4gdXBwZXJfYm91bmQpCiAgIHJldHVybihvdXRsaWVyX2luZCkKfQpoYW1wZWxfY291bnQgPC0gZnVuY3Rpb24oeCl7bGVuZ3RoKGhhbXBlbF9maWx0ZXIoeCkpfQpwY3RfY291bnQgPC0gZnVuY3Rpb24oeCl7bGVuZ3RoKHBlcmNlbnRpbGVfZmlsdGVyKHgpKX0KCm91dGxpZXJfY291bnRzIDwtIGRmX3RyYWluWywgY29udF9mZWF0c10gJT4lIG1hcF9kZnIoaGFtcGVsX2NvdW50KQpvdXRsaWVyX2NvdW50c1syLCBdIDwtIGRmX3RyYWluWywgY29udF9mZWF0c10gJT4lIG1hcF9kZnIocGN0X2NvdW50KQpvdXRsaWVyX2NvdW50cwpgYGAKCkZvciBjYXRlZ29yaWNhbCB2YXJpYWJsZXMsIHdlIHVzZSBzdGFja2VkIGJhciBwbG90cyB0byBzaG93IHRoZSBwZXJjZW50YWdlcyBvZiBvYnNlcnZhdGlvbnMgaW4gZWFjaCBjYXRlZ29yeSB0aGF0IGNvcnJlc3BvbmQgdG8gYHRhcmdldCA9PSAwYCBhbmQgYHRhcmdldCA9PSAxYCByZXNwZWN0aXZlbHkuIEEgbXVjaCBsYXJnZXIgcHJvcG9ydGlvbiBvZiBjbGFpbXMgd2l0aCBgY2F0MTMgPT0gQmAgYXBwZWFyIHRvIGJlIGFzc29jaWF0ZWQgd2l0aCBgdGFyZ2V0ID09IDFgIGNvbXBhcmVkIHRvIGBjYXQxMyA9PSBBYC4gT24gdGhlIG90aGVyIGhhbmQsIGEgbXVjaCBsYXJnZXIgcGVyY2VudGFnZSBvZiBjbGFpbXMgY29ycmVzcG9uZCB0byBgdGFyZ2V0ID09IDBgIGlmIGBjYXQxOGAgaXMgYEFgIG9yIGBCYCwgdGhhbiBpZiBgY2F0MThgIGlzIGBDYCBvciBgRGAuCgpgYGB7ciBjYXQtYnktdGFyZ2V0LCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFLCBmaWcud2lkdGg9MTUsIGZpZy5oZWlnaHQ9MTV9CiMgZmxhdHRlbiBkZiBpbnRvIHVzaW5nIHBpdm90X2xvbmdlcgojIGdyb3VwIGJ5IHRhcmdldCBhbmQgcGxvdCBkaXN0cmlidXRpb24KZGZbLCBjKGNhdF9mZWF0cywgdGFyZ2V0X2NvbCldICU+JSAKICBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJjYXQiKSwgbmFtZXNfdG8gID0gImNhdCIsIHZhbHVlc190bz0idmFsdWUiKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gdmFsdWUsIGZpbGw9dGFyZ2V0KSkgKyAKICAgIGdlb21fYmFyKHBvc2l0aW9uPSJmaWxsIikgKyAKICAgIHNjYWxlX3lfY29udGludW91cyhuYW1lID0gIldpdGhpbiBncm91cCBQZXJjZW50YWdlIiwgbGFiZWxzID0gc2NhbGVzOjpwZXJjZW50KSArCiAgICBmYWNldF93cmFwKH5jYXQsIHNjYWxlcz0iZnJlZV94IiwgbmNvbCA9IDQpICsKICAgIHRoZW1lX21pbmltYWwoYmFzZV9zaXplID0gNDApCmBgYAoKV2UgYWxzbyBpbnNwZWN0IHRoZSBjb3JyZWxhdGlvbiBtYXRyaXggZm9yIG91ciAqY29udGludW91cyogdmFyaWFibGVzLiBUaGVyZSBzZWVtcyB0byBiZSBhIGNsdXN0ZXIgb2YgdmFyaWFibGVzIC0gYGNvbnQxLCBjb250MiwgY29udDhgIC0gdGhhdCBhcmUgaGlnaGx5IGNvcnJlbGF0ZWQgd2l0aCBlYWNoIG90aGVyLiBUaGlzIGNvdWxkIHBvdGVudGlhbGx5IGxlYWQgdG8gcHJvYmxlbXMgd2l0aCBtdWx0aWNvbGxpbmVhcml0eSB3aGVuIHVzaW5nIGxpbmVhciBtb2RlbHMuIEluIGFkZGl0aW9uLCB3ZSBhbHNvIGNvbnNpZGVyIHRoZSBwZWFyc29uIGNvcnJlbGF0aW9uIGFuZCBvdXIgY29udGludW91cyB2YXJpYWJsZXMsIGFsdGhvdWdoIG5vdCBuZWNlc3NhcmlseSBtZWFuaW5nZnVsIGluIHRoaXMgY2FzZSBnaXZlbiBvdXIgdGFyZ2V0IGlzIGJpbmFyeSwgYW5kIGluIGFkZGl0aW9uIGdpdmVuIHRoZSBtdWx0aS1tb2RhbCBkaXN0cmlidXRpb25zIG9mIHRoZSBjb250aW51b3VzIHZhcmlhYmxlcyB3ZSBpZGVudGlmaWVkIGluIG91ciB1bml2YXJpYXRlIGV4cGxvcmF0b3J5IGRhdGEgYW5hbHlzaXMuIEhvd2V2ZXIsIHdlIG5vdGUgdGhhdCB0aGUgY29udGludW91cyB2YXJpYWJsZXMgaGF2ZSBwZWFyc29uIGNvcnJlbGF0aW9ucyBvZiByb3VnaGx5ICRbLTAuMiwgMC4yXSQsIHN1Z2dlc3RpbmcgdGhhdCB0aGVyZSBpcyBzb21lIHNpZ25hbCBiZXR3ZWVuIHRoZSBmZWF0dXJlcyBhbmQgdGhlIHRhcmdldC4gRmluYWxseSwgd2Ugbm90ZSB0aGF0IHRoZSBwZWFyc29uIGNvcnJlbGF0aW9uIG9ubHkgZGVzY3JpYmVzIGEgKmxpbmVhciogYW5kICpwYWlyd2lzZSogYXNzb2NpYXRpb24gYmV0d2VlbiB0aGUgdmFyaWFibGVzOyBhcyBzdWNoIHRoZXJlIGNvdWxkIGJlIGNvbXBsZXggbm9uLWxpbmVhciBhc3NvY2lhdGlvbnMgYW5kIGludGVyYWN0aW9ucyBiZXR3ZWVuIHRoZSB2YXJpYWJsZXMgYXMgd2VsbC4KCmBgYHtyIGNvci1tYXR9CmNvcl9tYXRyaXggPC0gY29yKGRmWywgY29udF9mZWF0c10pCmhlYXRtYXAoY29yX21hdHJpeCwgbWFpbj0iQ29ycmVsYXRpb24gTWF0cml4IChDbHVzdGVyZWQpIikKY29yX3dpdGhfdGFyZ2V0IDwtIHJvd25hbWVzX3RvX2NvbHVtbihkYXRhLmZyYW1lKGNvcihkZlssIGMoY29udF9mZWF0cyldLCBhcy5udW1lcmljKGRmJHRhcmdldCkpKSkKbmFtZXMoY29yX3dpdGhfdGFyZ2V0KSA8LSBjKCJmZWF0dXJlIiwgInBlYXJzb25fY29yciIpCmNvcl93aXRoX3RhcmdldCAlPiUKICBnZ3Bsb3QoYWVzKHg9cmVvcmRlcihmZWF0dXJlLCAtcGVhcnNvbl9jb3JyKSwgeSA9IHBlYXJzb25fY29ycikpICsgCiAgZ2VvbV9iYXIoc3RhdD0naWRlbnRpdHknKSArIGNvb3JkX2ZsaXAoKSArIGdndGl0bGUoIlBlYXJzb24gQ29ycmVsYXRpb24gb2YgQ29udGludW91cyB3aXRoIFRhcmdldCIpCmBgYAoKCldlIGNhbiB1c2UgUHJpbmNpcGFsIENvbXBvbmVudHMgQW5hbHlzaXMgKFBDQSkgYXMgYSBtZWFucyB0byB2aXN1YWxpc2UgdGhlIGRhdGEgaW4gbG93LWRpbWVuc2lvbiwgdG8gZGV0ZXJtaW5lIGlmIHRoZXJlIGFyZSBhbnkgZXhwbGljaXRseSBkaXNjZXJuaWJsZSB0cmVuZHMuIEJ5IGV5ZSwgdGhlIGNsYXNzZXMgZG8gbm90IGFwcGVhciB0byBiZSBsaW5lYXJseSBzZXBhcmFibGUgLSB3aGljaCBzdWdnZXN0IGEgbm9uLWxpbmVhciBtZXRob2QgbWF5IGJlIG1vcmUgZWZmZWN0aXZlLiBUaGVyZSBkbyBub3QgYXBwZWFyIHRvIGJlIGFueSBzaWduaWZpY2FudCBkaWZmZXJlbmNlIGluIHRoZSBQQ0EgcmVwcmVzZW50YXRpb25zIGZvciBlYWNoIGNsYXNzLCBhbHRob3VnaCB0aGVyZSBhcmUgbWFueSBvYnNlcnZhdGlvbnMgd2l0aCBgdGFyZ2V0ID09IDFgIGNsb3NlciB0byB0aGUgYm90dG9tIG9mIHRoZSBlbGxpcHNvaWQgZm9ybWVkIGJ5IHRoZSBmaXJzdCB0d28gUENBIGxvYWRpbmdzLiBXZSBub3RlIHRoYXQgdGhlcmUgaXMgYSBjb25uZWN0aW9uIGJldHdlZW4gUENBIGFuZCBSaWRnZSBbQGhhc3RpZTIwMDllbGVtZW50c10sIGFuZCBhbHNvIHRoYXQgdGhlIGZpcnN0IHR3byBwcmluY2lwYWwgY29tcG9uZW50cyBvbmx5IGNhcHR1cmUgYWJvdXQgJFxhcHByb3ggNjBcJSQgdmFyaWF0aW9uIGluIHRoZSAqY29udGludW91cyB2YXJpYWJsZXMqLgoKYGBge3IgcGNhLXZpen0KcGNzIDwtIHByY29tcChkZlssY29udF9mZWF0c10pCnNldC5zZWVkKDIwMjEpCmRhdGEuZnJhbWUocGMxPXBjcyR4WywxXSwgcGMyPXBjcyR4WywyXSwgdGFyZ2V0PWRmWywgInRhcmdldCJdKSAlPiUKZ2dwbG90KGFlcyh4ID0gcGMxLCB5ID0gcGMyLCBjb2xvdXIgPSB0YXJnZXQpKSArIAogIGdlb21faml0dGVyKGFscGhhPTAuNykgKyBnZ3RpdGxlKCdQcmluY2lwYWwgQ29tcG9uZW50cycpCiMgY3VtdWxhdGl2ZSB2YXJpYW5jZQpjdW11bF92YXIgPC0gY3Vtc3VtKHBjcyRzZGV2XjIgLyBzdW0ocGNzJHNkZXZeMikpCmdncGxvdChkYXRhLmZyYW1lKGZlYXR1cmUgPSAxOjExLCBjdW11bF92YXIgPSBjdW11bF92YXIpKSArIAogIGdlb21fbGluZShhZXMoeCA9IGZlYXR1cmUseSA9IGN1bXVsX3ZhcikpICsgZ2d0aXRsZSgiQ3VtdWxhdGl2ZSBFeHBsYWluZWQgVmFyaWFuY2UgUmF0aW8iKSArCiAgc2NhbGVfeV9jb250aW51b3VzKGxhYmVscz1wZXJjZW50KQpgYGAKCiMjIE1vZGVsbGluZwoKV2UgZmlyc3QgY29uc2lkZXIgYSBuYWl2ZSBtb2RlbCB0aGF0IGFsd2F5cyBwcmVkaWN0cyBhIHNpbmdsZSBsYWJlbCAoaW4gdGhpcyBjYXNlICQwJCkgZ2l2ZW4gaXQgaXMgdGhlIG1vc3QgZnJlcXVlbnRseSBvY2N1cnJpbmcgY2xhc3MuIEluIHRoaXMgY2FzZSwgdGhlIGFjY3VyYWN5IHdvdWxkICAkMSAtIFxoYXR7eX0gPSAwLjc0NSQgVGhpcyBpbGx1c3RyYXRlcyB0aGUgaXNzdWUgd2l0aCB0aGUgYWNjdXJhY3kgbWV0cmljIC0gdGhlICpuYWl2ZSogYWNjdXJhY3kgaXMgaGlnaCBkdWUgdG8gdGhlIG5hdHVyZSBvZiB0aGUgZGF0YSwgYW5kIGhlbmNlIHN1YnNlcXVlbnQgbW9kZWwgcGVyZm9ybWFuY2VzIG5lZWQgdG8gYmUgY29tcGFyZWQgd2l0aCB0aGlzIGJlbmNobWFyay4gCgpXZSBhbHNvIGNvbnNpZGVyIHRoZSAqKlJPQy1BVUMgbWV0cmljKiogKFJlY2VpdmluZyBPcGVyYXRvciBDaGFyYWN0ZXJpc3RpYyBBcmVhIFVuZGVyIHRoZSBDdXJ2ZSksIGFuZCAqKmFjY3VyYWN5KiogbWV0cmljLiBHaXZlbiB0aGUgcHJvYmxlbSBpcyBvbmUgcmVsYXRlZCB0byBpbnN1cmFuY2UsIHRoZSBtb2RlbGxpbmcgb3V0Y29tZSBvZiBpbnRlcmVzdCBpcyBub3Qgb25seSB0byBvYnRhaW4gdGhlIGNvcnJlY3QgcHJlZGljdGlvbnMgKGFjY3VyYWN5KSwgYnV0IGFsc28gYWNjdXJhdGUgcHJvYmFiaWxpdGllcywgd2hpY2ggaXMgd2hhdCB0aGUgQVVDIG1ldHJpYyBtZWFzdXJlcy4gQVVDIG1lYXN1cmVzIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgY2xhc3NpZmllciBhY3Jvc3MgYWxsIHBvc3NpYmxlIGRlY2lzaW9uIHRocmVzaG9sZHMsIHdoaWNoIG1ha2VzIGl0IG1vcmUgaGVscGZ1bCB0byBjb21wYXJlIHBlcmZvcm1hbmNlIHRoYW4gdGhlIGFjY3VyYWN5IG1ldHJpYyB3aXRoIGRlZmF1bHQgZGVjaXNpb24gdGhyZXNob2xkIHNldCB0byAwLjUuIEFzIHdlIGRvIG5vdCBrbm93IHRoZSBzcGVjaWZpYyB0aHJlc2hvbGQgcmVsZXZhbnQgdG8gdGhlIGluc3VyYW5jZSBjb250ZXh0IG9mIHRoZSBwcm9ibGVtLCB3ZSB3aWxsIHJlcG9ydCBib3RoIGFjY3VyYWN5IGFuZCBST0MgZm9yIGFsbCBtb2RlbHMsIGFuZCBjb21wYXJlIGl0IHRvIHRoYXQgb2YgdGhlIGJhc2VsaW5lIG1vZGVsIGluIFtzZWN0aW9uIDFdLiBPbiB0aGUgb3RoZXIgaGFuZCwgcHJlZGljdGluZyBhbGwgMHMgd291bGQgcmVzdWx0IGluIHRoZSBsb3dlc3QgUk9DLUFVQyBzY29yZSBvZiAwLjUgYXMgZXhwZWN0ZWQuCiAKCmBgYHtyfQojIHRyYWluLXRlc3QKWF90cmFpbiA9IGFzLm1hdHJpeChkZl90cmFpblssIGNvbnRfZmVhdHNdKQp5X3RyYWluID0gYXMubnVtZXJpYyhhcy5tYXRyaXgoZGZfdHJhaW4kdGFyZ2V0KSkKWF90ZXN0ID0gYXMubWF0cml4KGRmX3Rlc3RbLCBjb250X2ZlYXRzXSkKeV90ZXN0ID0gYXMubnVtZXJpYyhhcy5tYXRyaXgoZGZfdGVzdCR0YXJnZXQpKQoKZGlhZ25vc2lzIDwtIGZ1bmN0aW9uKHRyYWluX3ByZWQsIHRlc3RfcHJlZCwgdHJhaW5fdHJ1ZSwgdGVzdF90cnVlKXsKICB0cmFpbl9jbGFzc2VzIDwtIGlmZWxzZSh0cmFpbl9wcmVkID4gMC41LCAxLDApCiAgdGVzdF9jbGFzc2VzIDwtIGlmZWxzZSh0ZXN0X3ByZWQgPiAwLjUsIDEsMCkKICBhY2MxIDwtIG1lYW4odHJhaW5fY2xhc3NlcyA9PSB0cmFpbl90cnVlKQogIGF1YzEgPC0gYXVjKHJvYyh0cmFpbl90cnVlLCB0cmFpbl9wcmVkLCBxdWlldD1UUlVFKSkKICBhY2MyIDwtIG1lYW4odGVzdF9jbGFzc2VzID09IHRlc3RfdHJ1ZSkKICBhdWMyIDwtIGF1Yyhyb2ModGVzdF90cnVlLCB0ZXN0X3ByZWQsIHF1aWV0PVRSVUUpKQogIGRhdGEuZnJhbWUodHJhaW5fYWNjPWFjYzEsIHRyYWluX2F1Yz1hdWMxLCB0ZXN0X2FjYyA9IGFjYzIsIHRlc3RfYXVjPWF1YzIpCn0KCgpyZXN1bHRzID0gZGF0YS5mcmFtZShkaWFnbm9zaXMocmVwKDAsIGRpbShkZl90cmFpbilbMV0pLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlcCgwLCBkaW0oZGZfdGVzdClbMV0pLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpLAogICAgICAgICAgICAgICAgICAgICByb3cubmFtZXM9YygibmFpdmUiKSkKcmVzdWx0cwpgYGAKCiMjIyBMb2dpc3RpYyBSZWdyZXNzaW9uIChTR0QpCgpUbyBmdWxmaWxsIHRoZSBwcm9qZWN0IHJlcXVpcmVtZW50cywgd2UgZGVtb25zdHJhdGUgYSBgZnJvbSBzY3JhdGNoJyBTdG9jaGFzdGljIEdyYWRpZW50IERlc2NlbnQgcm91dGluZSAgZm9yIExvZ2lzdGljIFJlZ3Jlc3Npb24uIFRoZSBkZXJpdmlhdGlvbiBmb2xsb3dzIFtAaGFzdGllMjAwOWVsZW1lbnRzLCBwcC4gMTIwLTEyNl0KClRoZSAqKmxvZ2lzdGljIGxvc3MqKiBpcyBnaXZlbiBieToKJCRsKFxib2xkc3ltYm9se1xiZXRhfSkgPSAtXHN1bV97aSA9IDF9XntOfSB5X3tpfSBsb2cocCh4X3tpfSA7IFxib2xkc3ltYm9se1xiZXRhfSkpICsgKDEgLSB5X3tpfSkgbG9nKDEgLSBwKHhfe2l9IDsgXGJvbGRzeW1ib2x7XGJldGF9KSkgPSBcc3VtX3tpID0gMX1ee059IFxsZWZ0IFsgeV97aX1sb2cgXGxlZnQgKFxmcmFje3AoeF97aX0gOyBcYm9sZHN5bWJvbHtcYmV0YX0pfXsxIC0gcCh4X3tpfSA7IFxib2xkc3ltYm9se1xiZXRhfSl9IFxyaWdodCkgKyBsb2coMSAtIHAoeF97aX0gOyBcYm9sZHN5bWJvbHtcYmV0YX0pKSBccmlnaHQgXSQkCgokJCBsKFxib2xkc3ltYm9se1xiZXRhfSk9IC1cc3VtX3tpID0gMX1ee059XGxlZnQgW3lfe2l9IFxib2xkc3ltYm9se1xiZXRhfV57VH0geF97aX0gLSBsb2coMSArIGV4cChcYm9sZHN5bWJvbHtcYmV0YX1ee1R9eF97aX0pKSBccmlnaHQgXSQkCgpXaXRoIHRoZSBpbmNsdXNpb24gb2YgYSByZXVsYXJpc2F0aW9uIHRlcm0sIGluIHRoaXMgY2FzZSBhICRMXnsyfSQgcGVuYWx0eToKCiQkIGwoXGJvbGRzeW1ib2x7XGJldGF9KSA9IC1cc3VtX3tpID0gMX1ee059IFxsZWZ0IFt5X3tpfSBcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IHhfe2l9IC0gbG9nKDEgKyBleHAoXGJvbGRzeW1ib2x7XGJldGF9XntUfXhfe2l9KSkgXHJpZ2h0IF0gLSBcbGFtYmRhIFxib2xkc3ltYm9se1xiZXRhfV57VH0gXGJvbGRzeW1ib2x7XGJldGF9JCQKClRoZSBncmFkaWVudCBvZiB0aGUgbG9zcyBmdW5jdGlvbiBpcyBnaXZlbiBieToKCiQkXG5hYmxhKFxib2xkc3ltYm9se1xiZXRhfSkgPSAtXHN1bV97aSA9IDF9XntOfSBcbGVmdCBbIHlfe2l9IHhfe2l9IC0gXGZyYWN7eF97aX1leHAoXGJvbGRzeW1ib2x7XGJldGF9XntUfSB4X3tpfSl9ezEgKyBleHAoXGJvbGRzeW1ib2x7XGJldGF9XntUfSB4X3tpfSl9IFxyaWdodF0gLSBcbGFtYmRhIDJcYm9sZHN5bWJvbHtcYmV0YX0kJAoKV2UgdXNlIHRoZSBCYXJ6aWxhaS1Cb3J3ZWluIG1ldGhvZCBbQG11cnBoeTIwMTJtYWNoaW5lLCBwcC4gNDQ0LTQ0NV0gdG8gZGV0ZXJtaW5lIHRoZSBzdGVwIHNpemUuCgpgYGB7ciBncmFkaWVudC1kZXNjZW50fQojIGJpbmFyeSBjcm9zc2VudHJvcHkgLyBsb2ctbG9zcwpsb2dfbG9zcyA8LSBmdW5jdGlvbih4LCB5LCBiZXRhcywgbGFtYmRhKXsKICBsb2dpdHMgPC0geCAlKiUgYmV0YXMKICAtICh0KHkpICUqJSBsb2dpdHMgLSBzdW0obG9nKDEgKyBleHAobG9naXRzKSkpICsgbGFtYmRhICogdChiZXRhcykgJSolIGJldGFzKSAvIGRpbSh4KVsxXQp9CiMgbG9naXN0aWMgcmVncmVzc2lvbiBncmFkaWVudHMKZ3JhZGllbnRzIDwtIGZ1bmN0aW9uKHgsIHksIGJldGFzLCBsYW1iZGEpewogIGxvZ2l0cyA8LSB4ICUqJSBiZXRhcwogIC0gKHQoeCkgJSolICh5IC0gZXhwKGxvZ2l0cykvKDEgKyBleHAobG9naXRzKSkpKSAtIGxhbWJkYSAqMiAqIGJldGFzIC8gZGltKHgpWzFdCn0KcCA9IGRpbShYX3RyYWluKVsyXQpsYW1iZGEgPSAwCm5faXRlcnMgPC0gMTAwCmluaXRfc3RlcF9zaXplIDwtIDFlLTYKc2V0LnNlZWQoMjAyMSkKYmV0YV9pbml0IDwtIG1hdHJpeChybm9ybShwKSxucm93PXApCmJldGFfcGF0aCA8LSBtYXRyaXgocmVwKDAsIG5faXRlcnMgKiBwKSwgbnJvdyA9IG5faXRlcnMsIG5jb2w9cCkKYmV0YV9wYXRoWzEsXSA9IGJldGFfaW5pdApsYXN0X2dyYWQgPC0gZ3JhZCA8LSBncmFkaWVudHMoWF90cmFpbiwgeV90cmFpbiwgYmV0YV9wYXRoWzEsXSwgbGFtYmRhKQpiZXRhX3BhdGhbMixdID0gYmV0YV9pbml0IC0gaW5pdF9zdGVwX3NpemUgKiBncmFkCmdyYWQgPC0gZ3JhZGllbnRzKFhfdHJhaW4sIHlfdHJhaW4sIGJldGFfcGF0aFsyLF0sIGxhbWJkYSkKbG9zc2VzIDwtIHJlcCgwLCBuX2l0ZXJzKQpmb3IgKGkgaW4gMzpuX2l0ZXJzKXsKICAgIHN0ZXBfc2l6ZSA8LSBhcy5udW1lcmljKHQoYmV0YV9wYXRoW2kgLSAxLF0gLSBiZXRhX3BhdGhbaSAtIDIsXSkgJSolIChncmFkIC0gbGFzdF9ncmFkKSAvIAogICAgICAgICAgICAgICAgICAgICh0KGdyYWQgLSBsYXN0X2dyYWQpICUqJSAoZ3JhZCAtIGxhc3RfZ3JhZCkpKQogICAgYmV0YV9wYXRoW2ksXSA8LSBiZXRhX3BhdGhbaSAtIDEsXSAtIHN0ZXBfc2l6ZSAqIGdyYWQKICAgIGxhc3RfZ3JhZCA8LSBncmFkCiAgICBncmFkIDwtIGdyYWRpZW50cyhYX3RyYWluLCB5X3RyYWluLCBiZXRhX3BhdGhbaSwgXSwgbGFtYmRhKQogICAgbG9zc2VzW2ldIDwtIGxvZ19sb3NzKFhfdHJhaW4sIHlfdHJhaW4sIGJldGFfcGF0aFtpLF0sIGxhbWJkYSkKfQpnZ3Bsb3QoZGF0YS5mcmFtZShzdGVwID0gMzpuX2l0ZXJzLCBsb3NzPWxvc3Nlc1szOm5faXRlcnNdKSkgKyAKICBnZW9tX2xpbmUoYWVzKHggPSBzdGVwLCB5ID0gbG9zcykpICsKICBnZ3RpdGxlKCJCaW5hcnkgQ3Jvc3NlbnRyb3B5IHZzLiBJdGVyYXRpb25zIikKCnByZWRfdHJhaW4gPC0gYXMubnVtZXJpYygxIC8gKDEgKyBleHAoLVhfdHJhaW4gJSolIGJldGFfcGF0aFsxMDAsXSkpKQpwcmVkX3Rlc3QgPC0gYXMubnVtZXJpYygxIC8gKDEgKyBleHAoLVhfdGVzdCAlKiUgYmV0YV9wYXRoWzEwMCxdKSkpCnJlc3VsdHNbInNnZCIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJzZ2QiLF0KYGBgCgojIyMgTG9naXN0aWMgUmVncmVzc2lvbiAoRmV3IFByZWRpY3RvcnMpCgpBcyBhIGJhc2VsaW5lIG1vZGVsLCB3ZSBidWlsZCBhIHNpbXBsZSBsb2dpc3RpYyByZWdyZXNzaW9uIHdpdGggYSBmZXcgcHJlZGljdG9ycywgd2hpY2ggYXJlIHNlbGVjdGVkIGZyb20gb3VyIGV4cGxvcmF0b3J5IGRhdGEgYW5hbHlzaXMgdG8gaGF2ZSBkaXNjZXJuaWJsZSBkaWZmZXJlbmNlcyBpbiB0YXJnZXQuIFRoZXNlIGFyZSBgY29udDMsIGNvbnQ0LCBjYXQxMywgY2F0MThgLiBXZSB1c2UgdGhlIGBnbG1gIHBhY2thZ2UgdG8gZml0IGEgbG9naXN0aWMgcmVncmVzc2lvbi4KCmBgYHtyfQpnbG0xIDwtIGdsbSh0YXJnZXR+Y29udDMrY29udDQrY2F0MTMrY2F0MTgsZGF0YT1kZl90cmFpbiwgZmFtaWx5PWJpbm9taWFsKGxpbms9ImxvZ2l0IikpCnN1bW1hcnkoZ2xtMSkKYGBgCgpBbGwgZm91ciBwcmVkaWN0b3JzIGFyZSBzaWduaWZpY2FudCBhdCA1JSBsZXZlbCwgd2l0aCB0aGUgbW9zdCBzaWduaWZpY2FudCBwcmVkaWN0b3JzIGJlaW5nLi4uIFRoZSBjb2VmZmljaWVudHMgb2YgdGhlIGR1bW15IHZhcmlhYmxlcyBpbmRpY2F0ZSB0aGUgYXZlcmFnZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGxvZyBvZGRzIG9mIHRoYXQgZmFjdG9yIGxldmVsIGdyb3VwIGNvbXBhcmVkIHRvIHRoZSBiYXNlbGluZSBsZXZlbCBncm91cC4gSW4gb3VyIHJlZ3Jlc3Npb24sIHRoZSBmaXJzdCBjYXRlZ29yeSAoQSkgb2YgZWFjaCBjYXRlZ29yaWNhbCB2YXJpYWJsZSBpcyB0YWtlbiBhcyB0aGUgYmFzZWxpbmUgZ3JvdXAuIEZvciBleGFtcGxlLCB0aGUgY29lZmZpY2llbnQgb2YgYGNhdDEzYmAgaW1wbGllcyB0aGUgZm9sbG93aW5nIGVxdWF0aW9uOiAKJCRcdGV4dHtsb2dpdH0gUChcdGV4dHt0YXJnZXR9PTF8XHRleHR7Y2F0MTNifSA9IDEpIOKAkyBcdGV4dHtsb2dpdH0gUChcdGV4dHt0YXJnZXR9PTB8XHRleHR7Y2F0MTNifSA9IDEpID0gMS44NjgxLiAkJApJbiB3b3JkcywgdGhpcyBtZWFucyB0aGF0IGNsYWltcyB3aXRoIGBjYXQxM2IgPSAxYCBoYXZlIDMzJSBoaWdoZXIgbG9nIG9kZHMgb2YgdGFyZ2V0PTEgdGhhbiBjbGFpbXMgd2l0aCBgXHRleHR7Y2F0MTNifSA9PSAwYC4gSG93ZXZlciwgd2UgY2FuIG9ubHkgYXNzZXJ0IHRoYXQgdGhlcmUgaXMgc29tZSAgYXNzb2NpYXRpb24gLSBpbiB0aGlzIGNhc2UgaXQgaXMgc3RhdGlzdGljYWxseSBzaWduaWZpY2FudCByZWxhdGlvbnNoaXAgd2l0aCB0aGUgcC12YWx1ZSBiZWluZyBgMi4zNmUtMDhgIC0gYmV0d2VlbiB0aGUgcHJlc2VuY2Ugb2YgdGhlIHZhcmlhYmxlIGBjYXQxM2IgPSAxYCBhbmQgdGhlIHRhcmdldCBiZWluZyAxLCBidXQgbm90IHdoZXRoZXIgdGhlcmUgaXMgYSBjYXVzYXRpb247IGluIHBhcnRpY3VsYXIsIGdpdmVuIHRoZSBsYWNrIG9mIGtub3dsZWRnZSBvZiB3aGF0IHRoZSB2YXJpYWJsZSByZXByZXNlbnRzLCB3ZSBjYW5ub3QgZm9ybSBhbnkgbWVhbmluZ2Z1bCBoeXBvdGhlc2lzLgoKVG8gaW50ZXJwcmV0IHRoZSBjb2VmZmljaWVudHMgb2YgdGhlIGNvbnRpbnVvdXMgdmFyaWFibGVzLCByaXNrIHJhdGlvcyBuZWVkIHRvIGJlIGNhbGN1bGF0ZWQgdXNpbmcgc3BlY2lmaWMgcGFpcnMgb2YgdmFsdWVzIG9mIHRoZSBwcmVkaWN0b3JzLiBUaGUgbm9uLWxpbmVhcml0eSBvZiB0aGUgbG9naXN0aWMgZnVuY3Rpb24gbWVhbnMgdGhhdCBhIGNoYW5nZSBvZiBvbmUgdW5pdCBpbiB0aGUgdmFsdWUgb2YgYSBwcmVkaWN0b3IgaXMgbm90IHRoZSBzYW1lIGFjcm9zcyB0aGUgcmFuZ2Ugb2YgdGhlIHByZWRpY3Rvci4KCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CnByZWRfdHJhaW4gPC0gcHJlZGljdChnbG0xLCBkZl90cmFpbiwgdHlwZT0icmVzcG9uc2UiKQpwcmVkX3Rlc3QgPC0gcHJlZGljdChnbG0xLCBkZl90ZXN0LCB0eXBlPSJyZXNwb25zZSIpCnJlc3VsdHNbImdsbS1zbWFsbCIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJnbG0tc21hbGwiLF0KYGBgCgojIyMgTG9naXN0aWMgUmVncmVzc2lvbiAoQWxsIFByZWRpY3RvcnMpCgpXZSBub3cgcnVuIGEgbG9naXN0aWMgcmVncmVzc2lvbiB1c2luZyBhbGwgdmFyaWFibGVzLCB1c2luZyB0aGUgYGdsbWAgcGFja2FnZS4KYGBge3IgZ2xtLWZ1bGwtcmVzdWx0cywgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRSwgb3V0cHV0PUZBTFNFfQpnbG0yIDwtIGdsbSh0YXJnZXR+LiwgZGF0YT1kZl90cmFpbiwgZmFtaWx5PWJpbm9taWFsKGxpbms9ImxvZ2l0IiksIAogICAgICAgICAgICBjb250cm9sID0gbGlzdChtYXhpdCA9IDEwMCkpCiMgZGlzcGxheShnbG0yKQoKcHJlZF90cmFpbiA8LSBwcmVkaWN0KGdsbTIsIGRmX3RyYWluLCB0eXBlPSJyZXNwb25zZSIpCmdsbTIkeGxldmVscyA9IGxhcHBseShkZlssY2F0X2ZlYXRzXSwgbGV2ZWxzKQpwcmVkX3Rlc3QgPC0gcHJlZGljdChnbG0yLCBkZl90ZXN0LCB0eXBlPSJyZXNwb25zZSIpCnJlc3VsdHNbImdsbS1mdWxsIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbImdsbS1mdWxsIixdCiMgYW5vdmEoZ2xtMSwgZ2xtMiwgdGVzdD0iQ2hpc3EiKQpgYGAKCiMjIyBPdXRsaWVyIERldGVjdGlvbgpXZSBhdHRlbXB0IHRvIGRldGVjdCBvdXRsaWVycyB1bmRlciBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24uIEZvcm1hbGx5LCBvdXRsaWVycyBhcmUgZGVmaW5lZCBhcyBvYnNlcnZhdGlvbnMgd2l0aCBhIHJlc3BvbnNlIHZlY3RvciB0aGF0IGlzIHVudXN1YWwgY29uZGl0aW9uYWwgb24gY292YXJpYXRlcy4gVGhleSBhcmUgZm9ybWFsbHkgaWRlbnRpZmllZCB0aHJvdWdoIHN0dWRlbnRpemVkIHJlc2lkdWFscy4gSW50dWl0aXZlbHksIG91dGxpZXJzIGhhdmUgbGFyZ2UgcmVzaWR1YWxzIGFuZCB3ZSBjYW4gZm9ybWFsbHkgdGVzdCAoYnkgbG9va2luZyBhdCB0aGUgQm9uZmVycm9uaS0tYWRqdXN0ZWQgcC12YWx1ZXMpIGlmIHRoZXNlIHJlc2lkdWFscyBhcmUgc2lnbmlmaWNhbnRseSBsYXJnZXIgdGhhbiB0aGUgb3RoZXIgb2JzZXJ2YXRpb25zLiBXZSB1c2UgdGhlIGBvdXRsaWVyVGVzdGAgZnVuY3Rpb24gZnJvbSB0aGUgYGNhcmAgdG8gZGV0ZXJtaW5lIHRoZSBvdXRsaWVycyBmcm9tIHRoZSBgZ2xtYCBtb2RlbC4KCk9ic2VydmF0aW9ucyB0aGF0IGFyZSBmYXIgZnJvbSB0aGUgYXZlcmFnZSBjb3ZhcmlhdGUgcGF0dGVybiBhcmUgY29uc2lkZXJlZCB0byBoYXZlIGhpZ2ggbGV2ZXJhZ2UgYW5kIGNhbiBiZSBtZWFzdXJlZCB1c2luZyB0aGUgaGF0IHZhbHVlLiBIZXJlLCB0aGVyZSBhcmUgbWFueSBwb2ludHMgd2l0aCBoaWdoIGxldmVyYWdlLiAKCmBgYHtyfQpvdXRsaWVyVGVzdChnbG0yKQpvdXRsaWVycyA8LSBhcy5udW1lcmljKG5hbWVzKG91dGxpZXJUZXN0KGdsbTIpJHApKQpgYGAKCkZpbmFsbHksIHdlIG1lYXN1cmUgZm9yIGluZmx1ZW5jZSwgd2hpY2ggaXMgYW4gb2JzZXJ2YXRpb24gdGhhdCBpcyBhbiBvdXRsaWVyIGFuZCBoYXZlIGhpZ2ggbGV2ZXJhZ2UuIFRoZXNlIGFyZSBsaWtlbHkgdG8gaW5mbHVlbmNlIHRoZSByZWdyZXNzaW9uIGNvZWZmaWNpZW50cyBhbmQgaW5mbHVlbmNlIGNhbiBiZSB0aG91Z2h0IG9mIGFzIHRoZSBwcm9kdWN0IG9mIGxldmVyYWdlIGFuZCBvdXRsaWVyLiBIZXJlLCB3ZSBwbG90IHN0dWRlbnRpc2VkIHJlc2lkdWFscyBhZ2FpbnN0IGhhdC12YWx1ZXMgd2l0aCB0aGUgc2l6ZSBvZiBhIGNpcmNsZSBiZWluZyBwcm9wb3J0aW9uYWwgdG8gdGhlIENvb2sncyBkaXN0YW5jZSBvZiBhbiBvYnNlcnZhdGlvbi0gYSBtZWFzdXJlIG9mIGluZmx1ZW5jZS4KCgpgYGB7cn0KaW5mbHVlbmNlSW5kZXhQbG90KGdsbTIsIHZhcnMgPSAiaGF0IikKYGBgCgpgYGB7cn0KaW5mbHVlbmNlUGxvdChnbG0yKQpgYGAKSGVyZSwgd2Ugb2JzZXJ2ZSB0aGF0IHRoZXJlIGFyZSBhIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgd2l0aCBoaWdoIGluZmx1ZW5jZSAtIG91dGxpZXJzIHdpdGggaGlnaCBsZXZlcmFnZS4gVGh1cywgd2UgcmVtb3ZlIHRoZXNlIG9ic2VydmF0aW9ucyBhbmQgY29tcGFyZSB0aGUgcGVyZm9ybWFuY2Ugb2Ygb3VyIHVwZGF0ZWQgbW9kZWwgd2l0aCB0aGUgb3JpZ2luYWwgbW9kZWwuIAoKSW4gdGhlIGxhdGVyIG1vZGVscywgd2Ugd2lsbCBhbHNvIGV4Y2x1ZGUgdGhlIHNhbWUgb3V0bGllcnMuIAoKYGBge3IgaW5mbHVlbmNlcnN9CmluZmx1ZW5jZXJzIDwtIGFzLm51bWVyaWMocm93bmFtZXMoaW5mbHVlbmNlUGxvdChnbG0yKSkpCmdsbTJfaW5mbHVlbmNlcnMgPC0gdXBkYXRlKGdsbTIsIHN1YnNldCA9IGMoLWluZmx1ZW5jZXJzKSkKZ2xtMl9vdXRsaWVycyA8LSB1cGRhdGUoZ2xtMiwgc3Vic2V0ID0gYygtb3V0bGllcnMpKQpyZW1vdmFsX2xpc3QgPC0gdW5pb24ob3V0bGllcnMsIGluZmx1ZW5jZXJzKQpnbG0yX3JlbW92ZWQgPC0gdXBkYXRlKGdsbTIsIHN1YnNldCA9IGMoLXJlbW92YWxfbGlzdCkpCmNvbXBhcmVDb2VmcyhnbG0yLCBnbG0yX2luZmx1ZW5jZXJzLCBnbG0yX291dGxpZXJzLCBnbG0yX3JlbW92ZWQpCiMgYWN0dWFsbHkganVzdCB1c2UgZ2xtMiBhbmQgZ2xtMl9yZW1vdmVkCmBgYAoKCgojIyMgUmVndWxhcmlzZWQgTG9naXN0aWMgUmVncmVzc2lvbgoKR2l2ZW4gdGhlIGlzc3VlIG9mICpoaWdoIGRpbWVuc2lvbmFsaXR5Kiwgd2UgY29uc2lkZXIgYSByZWd1bGFyaXNlZCBmb3JtIG9mIGxvZ2lzdGljIHJlZ3Jlc3Npb24uIFdlIHVzZSB0aGUgYGdsbW5ldGAgcGFja2FnZTsgaW4gZG9pbmcgc28gd2UgbmVlZCB0byBjb252ZXJ0IHRoZSBkYXRhIHR5cGUgaW50byBtYXRyaWNlcy5UaGUgYGdsbW5ldGAgcGFja2FnZSByZXF1aXJlcyB0aGUgZGF0YSB0byBiZSBpbiBhICptYXRyaXgqIGRhdGEgdHlwZSwgYW5kIGhlbmNlIHdlIG1ha2UgdGhlIGNvcnJlc3BvbmRpbmcgYWRqdXN0bWVudC4KCmBgYHtyIGdsbS1yaWRnZS1zY29yZXMsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9ClhfdHJhaW4gPSBkZl90cmFpblssIC1sZW5ndGgoZGZfdHJhaW4pXQp5X3RyYWluIDwtIGRmX3RyYWluJHRhcmdldApYX3Rlc3QgPSBkZl90ZXN0WywgLWxlbmd0aChkZl90ZXN0KV0KeV90ZXN0IDwtIGRmX3Rlc3QkdGFyZ2V0ClhfdHJhaW4gPSBtb2RlbC5tYXRyaXgofi4sIFhfdHJhaW4pClhfdGVzdCA9IG1vZGVsLm1hdHJpeCh+LiwgWF90ZXN0KQpnbG0zIDwtIGN2LmdsbW5ldChYX3RyYWluLCB5X3RyYWluLCAKICAgICAgICAgICAgICAgICAgZmFtaWx5PSJiaW5vbWlhbCIobGluaz0ibG9naXQiKSwgYWxwaGE9MCkKZ2xtMwpwcmVkX3RyYWluIDwtIGFzLm51bWVyaWMocHJlZGljdChnbG0zLCBYX3RyYWluLCB0eXBlPSJyZXNwb25zZSIpKQpwcmVkX3Rlc3QgPC0gYXMubnVtZXJpYyhwcmVkaWN0KGdsbTMsIFhfdGVzdCwgdHlwZT0icmVzcG9uc2UiKSkKcmVzdWx0c1siZ2xtLXJpZGdlIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbImdsbS1yaWRnZSIsXQpgYGAKCiMjIyBSYW5kb20gRm9yZXN0CgpUbyBpbXByb3ZlIHBlcmZvcm1hbmNlLCB3ZSBkcmF3IG9uIHRoZSB1c2FnZSBvZiBub24tbGluZWFyIHRyZWUtYmFzZWQgbW9kZWxzLCBzcGVjaWZpY2FsbHkgKipSYW5kb20gRm9yZXN0cyoqIFtAaGFzdGllMjAwOWVsZW1lbnRzXS4gSW50dWl0aXZlbHksIGEgcmFuZG9tIGZvcmVzdCBhdmVyYWdlcyBkaWZmZXJlbnQgZGVjaXNpb24gdHJlZXMgKGtub3duIGFzIGJhZ2dpbmcpIHNvIGFzIHRvIHJlZHVjZSB0aGUgdmFyaWFuY2Ugb2YgaW5kaXZpZHVhbCB0cmVlcy4gV2UgdXNlIHRoZQoKYGBge3IgcmYgLG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0KcmZfcmVjaXBlIDwtIHJlY2lwZSh0YXJnZXR+LiwgZGF0YSA9IGRmX3RyYWluKQoKcmZfbW9kZWwgPC0gCiAgcmFuZF9mb3Jlc3QodHJlZXM9MTAwKSAlPiUKICBzZXRfZW5naW5lKCJyYW5nZXIiLCBpbXBvcnRhbmNlPSJpbXB1cml0eSIsIHNlZWQ9MjAyMSkgJT4lCiAgc2V0X21vZGUoImNsYXNzaWZpY2F0aW9uIikKCnJmX3dvcmtmbG93IDwtIHdvcmtmbG93KCkgJT4lCiAgYWRkX3JlY2lwZShyZl9yZWNpcGUpICU+JQogIGFkZF9tb2RlbChyZl9tb2RlbCkKCnJmMSA8LSBmaXQocmZfd29ya2Zsb3csIGRmX3RyYWluKQpyYW5nZXJfb2JqIDwtIHB1bGxfd29ya2Zsb3dfZml0KHJmMSkkZml0CiMgcGxvdCBmZWF0dXJlIGltcG9ydGFuY2VzCnJmX2ZlYXRfaW1wIDwtIHJvd25hbWVzX3RvX2NvbHVtbihkYXRhLmZyYW1lKHJhbmdlcl9vYmokdmFyaWFibGUuaW1wb3J0YW5jZSkpOwpuYW1lcyhyZl9mZWF0X2ltcCkgPC0gYygiZmVhdCIsICJpbXBvcnRhbmNlIikKZ2dwbG90KHJmX2ZlYXRfaW1wLCBhZXMoeCA9IHJlb3JkZXIoZmVhdCwgaW1wb3J0YW5jZSksIHkgPSBpbXBvcnRhbmNlKSkrIAogICAgICBnZW9tX2JhcihzdGF0PSJpZGVudGl0eSIsIHBvc2l0aW9uPSJkb2RnZSIpKyBjb29yZF9mbGlwKCkrCiAgICAgIHlsYWIoIkZlYXR1cmUgSW1wb3J0YW5jZSAoR2luaSBJbXB1cml0eSkiKSsKICAgICAgeGxhYigiRmVhdHVyZSIpKwogICAgICBnZ3RpdGxlKCJSYW5kb20gRm9yZXN0IEZlYXR1cmUgSW1wb3J0YW5jZXMiKQojZXZhbHVhdGUgbWV0cmljcwpwcmVkX3RyYWluIDwtIHVubGlzdChwcmVkaWN0KHJmMSxkZl90cmFpbix0eXBlPSdwcm9iJylbLDJdKQpwcmVkX3Rlc3QgPC0gdW5saXN0KHByZWRpY3QocmYxLCBkZl90ZXN0LCB0eXBlPSdwcm9iJylbLDJdKQpyZXN1bHRzWyJyZiIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJyZiIsXQpgYGAKCmBgYHtyIHBkcCwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KdGVtcCA8LSBmdW5jdGlvbih4KXtwYXJ0aWFsKHJhbmdlcl9vYmosIHRyYWluPWRmX3RyYWluLCBwcmVkLnZhciA9IHgsIHBsb3QgPSBUUlVFLCBwbG90LmVuZ2luZSA9ICJnZ3Bsb3QyIiwgcGFyb3B0cyA9IGxpc3QoLnBhY2thZ2VzID0gInJhbmdlciIpKX0KcGxvdHMgPC0gbGFwcGx5KG5hbWVzKGRmX3RyYWluKVtjb250X2ZlYXRzXSwgdGVtcCkKd3JhcF9wbG90cyhwbG90cykKYGBgCgpUaGUgcmFuZG9tIGZvcmVzdCBoYXMgYSB0ZXN0IGFjY3VyYWN5IG9mIDAuODM2IGFuZCBhIHRlc3QgQVVDIG9mIDAuODcyLCB3aGljaCBpcyBoaWdoZXIgdGhhbiB0aGUgcHJldmlvdXMgbGluZWFyIG1vZGVscy4gSG93ZXZlciwgdGhlIHRyYWluIGFjY3VyYWN5IGFuZCBBVUMgYXJlIHNpZ25pZmljYW50bHkgaGlnaGVyIHRoYW4gdGhlIHRlc3QgcGVyZm9ybWFuY2UsIHdoaWNoIHN1Z2dlc3QgdGhhdCB0aGVyZSBtYXkgYmUgc29tZSBkZWdyZWUgb2Ygb3ZlcmZpdHRpbmcgdG8gdGhlIHRyYWluIGRhdGEuIAoKUmFuZG9tIGZvcmVzdHMgY2FuIGJlIHVzZWQgdG8gcmFuayB0aGUgaW1wb3J0YW5jZSBvZiBkaWZmZXJlbnQgZmVhdHVyZXMuIFNwZWNpZmljYWxseSwgdGhlIHgtYXhpcyBpcyB0aGUgTWVhbiBEZWNyZWFzZSBBY2N1cmFjeSwgd2hpY2ggcmVwb3J0cyBob3cgbXVjaCBhY2N1cmFjeSB0aGUgbW9kZWwgbG9zZXMgd2hlbiB3ZSBleGNsdWRlIHRoaXMgdmFyaWFibGUuIFRoZSBtb3JlIHRoZSBhY2N1cmFjeSBmYWxscyBieSwgdGhlIG1vcmUgaW1wb3J0YW50IHRoZSBwYXJ0aWN1bGFyIHZhcmlhYmxlIGlzLiBOb3RlIGhlcmUgdGhhdCBmb3IgY2F0ZWdvcmljYWwgdmFyaWFibGVzLCBlYWNoIGxldmVsIG9mIHRoZSBjYXRlZ29yeSBpcyBjbGFzc2lmaWVkIGFzIGEgc2luZ2xlIHZhcmlhYmxlLiBJbiB0aGlzIHBsb3QsIHdlIHJlY29yZGVkIHRoZSAzMCBtb3N0IGltcG9ydGFudCB2YXJpYWJsZXMuIAoKV2UgdGhlbiBydW4gYW5vdGhlciByYW5kb20gZm9yZXN0IHdpdGggdGhlIG1vc3QgaW1wb3J0YW50IGZlYXR1cmVzLiBJbiBkb2luZyBzbywgd2UgaG9wZSB0byByZWR1Y2UgdGhlIGRlZ3JlZSBvZiBvdmVyZml0dGluZyBieSByZWR1Y2luZyB0aGUgY29tcGxleGl0eSBvZiB0aGUgbW9kZWwuIEhvd2V2ZXIsIGl0IGRvZXMgbm90IG1ha2Ugc2Vuc2UgdG8gZHJvcCBzb21lIGxldmVscyBvZiBhIGNhdGVnb3JpY2FsIHZhcmlhYmxlIHdoaWxlIGluY2x1ZGluZyB0aGUgb3RoZXIgbGV2ZWxzLiBIZW5jZSwgYXMgbG9uZyBhcyBhIGxldmVsIGlzIHByZXNlbnQgaW4gdGhlIHRvcCAzMCBmZWF0dXJlcywgd2Ugd2lsbCBpbmNsdWRlIHRoZSBlbnRpcmUgY2F0ZWdvcnkgaW4gb3VyIHVwZGF0ZWQgcmFuZG9tIGZvcmVzdCBtb2RlbC4gVGhpcyByZXN1bHRzIGluIHVzIGtlZXBpbmcgb25seSAyMiB2YXJpYWJsZXMsIGZyb20gYW4gaW5pdGlhbCAzMC4gCgpPdXIgcmVkdWNlZCByYW5kb20gZm9yZXN0IGhhcyBhIHNsaWdodGx5IGltcHJvdmVkIHRlc3QgYWNjdXJhY3kgYW5kIGEgc2xpZ2h0bHkgZGVjcmVhc2VkIHRlc3QgQVVDLiBIb3dldmVyLCBpdCBkb2VzIG5vdCBzb2x2ZSB0aGUgcG90ZW50aWFsIHByb2JsZW0gb2Ygb3ZlcmZpdHRpbmcgYXMgdHJhaW4gcGVyZm9ybWFuY2UgaXMgc3RpbGwgc2lnbmlmaWNhbnRseSBiZXR0ZXIgdGhhbiB0ZXN0IHBlcmZvcm1hbmNlLiBJbiBmYWN0LCB0cmFpbiBwZXJmb3JtYW5jZSBvbiB0aGUgcmVkdWNlZCByYW5kb20gZm9yZXN0IGlzIGJldHRlciB0aGFuIHRoZSByYW5kb20gZm9yZXN0IHdpdGggYSBmdWxsIHNldCBvZiB2YXJpYWJsZXMgLSB0aGUgcmVkdWNlZCBjb21wbGV4aXR5IG9mIHRoZSBtb2RlbCBlbmFibGVkIGl0IHRvIGhhdmUgYSBsb3dlciBiaWFzIG9uIHRoZSB0cmFpbmluZyBzZXQuIAoKIyMjIFhHQm9vc3QKCkZvciBjb21wbGV0ZW5lc3MsIHdlIGFsc28gY29uc2lkZXIgdGhlIGB4Z2Jvb3N0YCBsaWJyYXJ5IGZvciAqKmdyYWRpZW50IGJvb3N0ZWQgZGVjaXNpb24gdHJlZXMqKi4gR3JhZGllbnQgQm9vc3RlZCBEZWNpc2lvbiBUcmVlcy4gVGhlIFhHQm9vc3QgcGFja2FnZSwgaW50cm9kdWNlZCBpbiBbQGNoZW4yMDE2eGdib29zdF0gaXMgYSB2YXJpYW50IG9mIEdyYWRpZW50IEJvb3N0ZWQgRGVjaXNpb24gVHJlZXMgW0BoYXN0aWUyMDA5ZWxlbWVudHMsIHBwLiAzNTMtMzc0XQoKYGBge3IgeGdiLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpkbXlfdHJhaW4gPC0gZHVtbXlWYXJzKCJ+LiIsIGRhdGEgPSBkZl90cmFpblssLWxlbmd0aChkZl90cmFpbildKQpkbXlfdGVzdCA8LSBkdW1teVZhcnMoIn4uIiwgZGF0YSA9IGRmX3Rlc3RbLC1sZW5ndGgoZGZfdGVzdCldKQpYX3RyYWluIDwtIGFzLm1hdHJpeChkYXRhLmZyYW1lKHByZWRpY3QoZG15X3RyYWluLGRmX3RyYWluKSkpClhfdGVzdCA8LSBhcy5tYXRyaXgoZGF0YS5mcmFtZShwcmVkaWN0KGRteV90ZXN0LGRmX3Rlc3QpKSkKeV90cmFpbiA9IGFzLmludGVnZXIoYXMubWF0cml4KGRmX3RyYWluJHRhcmdldCkpCnlfdGVzdCA9IGFzLmludGVnZXIoYXMubWF0cml4KGRmX3Rlc3QkdGFyZ2V0KSkKYnN0IDwtIHhnYm9vc3QoZGF0YSA9IFhfdHJhaW4sIGxhYmVsPXlfdHJhaW4sIG1heF9kZXB0aCA9IDIsIG5yb3VuZCA9IDEwLCAKICAgICAgICAgICAgICAgdmVyYm9zZT0wLAogICAgICAgICAgICAgICBvYmplY3RpdmU9J2JpbmFyeTpsb2dpc3RpYycsCiAgICAgICAgICAgICAgIGV2YWxfbWV0cmljPSJsb2dsb3NzIikKCnByZWRfdHJhaW4gPC0gcHJlZGljdChic3QsIFhfdHJhaW4sIHR5cGU9InJlc3BvbnNlIikKcHJlZF90ZXN0IDwtIHByZWRpY3QoYnN0LCBYX3Rlc3QsIHR5cGU9InJlc3BvbnNlIikKcmVzdWx0c1sieGdiIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbInhnYiIsXQoKaW1wb3J0YW5jZV9tYXRyaXggPC0geGdiLmltcG9ydGFuY2UobW9kZWw9YnN0KQp4Z2IucGxvdC5pbXBvcnRhbmNlKGltcG9ydGFuY2VfbWF0cml4KQojIHNoYXBsZXkgdmFsdWVzICAKeGdib29zdDo6eGdiLmdncGxvdC5zaGFwLnN1bW1hcnkoWF90ZXN0LCBtb2RlbCA9IGJzdCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRhcmdldF9jbGFzcyA9IDEsIHRvcF9uID0gMjApICAjIFN1bW1hcnkgcGxvdApgYGAKCiMjIyBDYXRCb29zdAoKV2UgYWxzbyBjb25zaWRlciBicmllZmx5IGV4YW1pbmUgdGhlIGBjYXRib29zdGAgbGlicmFyeSBmb3IgKipncmFkaWVudCBib29zdGVkIGRlY2lzaW9uIHRyZWVzKiosIGdpdmVuIGl0cyBwb3B1bGFyaXR5IG9uIG1hY2hpbmUgbGVhcm5pbmcgY29tcGV0aXRpb25zIHN1Y2ggYXMgS2FnZ2xlLiBUaGUgQ2F0Qm9vc3QgbGlicmFyeSBoYXMgdGhlIGFkdmFudGFnZSBvZiBsZWFybmluZyBhIHRhcmdldCBlbmNvZGluZyBmb3IgY2F0ZWdvcmljYWwgdmFyaWFibGVzLiBGcm9tIGFuIGltcGxlbWVudGF0aW9uIHBvaW50IG9mIHZpZXcsIHRoaXMgbWF5IHJlZHVjZSB0aGUgcHJlcHJvY2Vzc2luZyB0aGF0IG1heSBiZSByZXF1aXJlZC5Gb3IgZGV0YWlscyBvbiBDYXRCb29zdCwgcmVmZXIgdG8gW0Bwcm9raG9yZW5rb3ZhMjAxN2NhdGJvb3N0XQoKYGBge3IgY2IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9ClhfdHJhaW4gPSBkZl90cmFpblssYyhjYXRfZmVhdHMsIGNvbnRfZmVhdHMpXQp5X3RyYWluID0gYXMuaW50ZWdlcihkZl90cmFpbiR0YXJnZXQpClhfdGVzdCA9IGRmX3Rlc3RbLGMoY2F0X2ZlYXRzLCBjb250X2ZlYXRzKV0KeV90ZXN0ID0gYXMuaW50ZWdlcihkZl90ZXN0JHRhcmdldCkKCnBvb2wgPC0gY2F0Ym9vc3QubG9hZF9wb29sKFhfdHJhaW4sIHlfdHJhaW4sIGNhdF9mZWF0dXJlcyA9IGNhdF9mZWF0cykKbW9kZWwgPC0gY2F0Ym9vc3QudHJhaW4ocG9vbCwgcGFyYW1zPWxpc3QoZGVwdGggPSA4LCBpdGVyYXRpb25zID0gMTAsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsb3NzX2Z1bmN0aW9uPSdMb2dsb3NzJywgdmVyYm9zZT0wKSkKCnByZWRfdHJhaW4gPC0gY2F0Ym9vc3QucHJlZGljdChtb2RlbCwgY2F0Ym9vc3QubG9hZF9wb29sKFhfdHJhaW4pLCBwcmVkaWN0aW9uX3R5cGUgPSAnUHJvYmFiaWxpdHknKQpwcmVkX3Rlc3QgPC0gY2F0Ym9vc3QucHJlZGljdChtb2RlbCwgY2F0Ym9vc3QubG9hZF9wb29sKFhfdGVzdCksIHByZWRpY3Rpb25fdHlwZSA9ICdQcm9iYWJpbGl0eScpCgojIGZlYXR1cmUgaW1wb3J0YW5jZQpmZWF0X2ltcG9ydGFuY2UgPC0gY2F0Ym9vc3QuZ2V0X2ZlYXR1cmVfaW1wb3J0YW5jZShtb2RlbCwgcG9vbCkKaW1wb3J0YW5jZXMgPC0gZGF0YS5mcmFtZShmZWF0X2ltcG9ydGFuY2Vbb3JkZXIoZmVhdF9pbXBvcnRhbmNlLCBkZWNyZWFzaW5nPUZBTFNFKSxdKQppbXBvcnRhbmNlcyRmZWF0dXJlcyA9IHJvd25hbWVzKGltcG9ydGFuY2VzKQpuYW1lcyhpbXBvcnRhbmNlcykgPC0gYygiaW1wb3J0YW5jZSIsImZlYXR1cmVzIikKaW1wb3J0YW5jZXMkZmVhdHVyZXMgPC0gZmFjdG9yKGltcG9ydGFuY2VzJGZlYXR1cmVzLCBsZXZlbD1pbXBvcnRhbmNlcyRmZWF0dXJlcykKZ2dwbG90KGltcG9ydGFuY2VzLCBhZXMoeD1pbXBvcnRhbmNlLCB5PWZlYXR1cmVzKSkgKyAKICBnZW9tX2JhcihzdGF0PSJpZGVudGl0eSIpICsKICBnZ3RpdGxlKCJDYXRCb29zdCBGZWF0dXJlIEltcG9ydGFuY2UiKQoKI1NoYXBsZXkgVmFsdWVzCmRhdGFfc2hhcF90cmVlIDwtIGNhdGJvb3N0LmdldF9mZWF0dXJlX2ltcG9ydGFuY2UobW9kZWwsIHBvb2wgPSBwb29sLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHR5cGUgPSAiU2hhcFZhbHVlcyIpCmRhdGFfc2hhcF90cmVlIDwtIGRhdGEuZnJhbWUoZGF0YV9zaGFwX3RyZWVbLCAtbmNvbChkYXRhX3NoYXBfdHJlZSldKSAKbmFtZXMoZGF0YV9zaGFwX3RyZWUpID0gbmFtZXMoZGZbLCBjKGNhdF9mZWF0cywgY29udF9mZWF0cyldKQoKZ2dwbG90KHN0YWNrKGRhdGFfc2hhcF90cmVlKSwgYWVzKHggPSBpbmQsIHkgPSB2YWx1ZXMpKSArCiAgICBnZW9tX3BvaW50KGFlcyhjb2xvciA9IHZhbHVlcykpICsgY29vcmRfZmxpcCgpICsgCiAgICBnZ3RpdGxlKCJTaGFwbGV5IFZhbHVlcyBieSB2YXJpYWJsZSIpICArIHNjYWxlX2NvbG9yX3ZpcmlkaXNfYygpCgpyZXN1bHRzWyJjYXRib29zdCIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJjYXRib29zdCIsXQpgYGAKCiMjIFJlc3VsdHMgYW5kIEV2YWx1YXRpb24KCmBgYHtyfQpyZXN1bHRzCnJlc3VsdHNbb3JkZXIoLXJlc3VsdHMkdGVzdF9hdWMsIC1yZXN1bHRzJHRlc3RfYWNjKSxdCmBgYAoKQWx0aG91Z2ggdGhlIHRyZWUtYmFzZWQgbWV0aG9kcyBhcmUgbGVzcyBpbnRlcnByZXRhYmxlIGFuZCBtb3JlICJibGFjayBib3giIHRvIHNvbWUgZXh0ZW50LCB3ZSBjYW4gbWFrZSB1c2Ugb2YgbW9kZWwgaW50ZXJwcmV0YWJpbGl0eSB0ZWNobmlxdWVzLgoKIyMgQmlibGlvZ3JhcGh5Cgo6OjogeyNyZWZzfQo6OjoKCiMjIEFwcGVuZGl4CgpgYGB7cn0Kc2V0LnNlZWQoMjAyMSkKY3Zfc3BsaXRzIDwtIHJzYW1wbGU6OnZmb2xkX2N2KGRmX3RyYWluLCBzdHJhdGEgPSB0YXJnZXQsIHY9IDMpCm1vZCA8LSBsb2dpc3RpY19yZWcocGVuYWx0eSA9IHR1bmUoKSwKICAgICAgICAgICAgICAgICAgICBtaXh0dXJlID0gdHVuZSgpKSAlPiUKICBzZXRfZW5naW5lKCJnbG1uZXQiKQoKZ2xtbmV0X3JlY2lwZSA8LSByZWNpcGUodGFyZ2V0fi4sZGF0YSA9IGRmX3RyYWluKSAlPiUgCiAgc3RlcF9kdW1teShhbGxfbm9taW5hbCgpLCAtYWxsX291dGNvbWVzKCkpCgpnbG1uZXRfd29ya2Zsb3c8LSB3b3JrZmxvdygpICU+JQogIGFkZF9yZWNpcGUoZ2xtbmV0X3JlY2lwZSkgJT4lCiAgYWRkX21vZGVsKG1vZCkKCmdsbW5fc2V0IDwtIHBhcmFtZXRlcnMocGVuYWx0eShyYW5nZSA9IGMoLTUsMSksIHRyYW5zID0gbG9nMTBfdHJhbnMoKSksCiAgICAgICAgICAgICAgICAgICAgICAgbWl4dHVyZSgpKQoKZ2xtbl9ncmlkIDwtIAogIGdyaWRfcmVndWxhcihnbG1uX3NldCwgbGV2ZWxzID0gYyg3LCA1KSkKY3RybCA8LSBjb250cm9sX2dyaWQoc2F2ZV9wcmVkID0gVFJVRSwgdmVyYm9zZSA9IFRSVUUpCgpnbG1uX3R1bmUgPC0gCiAgdHVuZV9ncmlkKGdsbW5ldF93b3JrZmxvdywKICAgICAgICAgICAgcmVzYW1wbGVzID0gY3Zfc3BsaXRzLAogICAgICAgICAgICBncmlkID0gZ2xtbl9ncmlkLAogICAgICAgICAgICBtZXRyaWNzID0gbWV0cmljX3NldChyb2NfYXVjKSwKICAgICAgICAgICAgY29udHJvbCA9IGN0cmwpCgoKYmVzdF9nbG1uIDwtIHNlbGVjdF9iZXN0KGdsbW5fdHVuZSwgbWV0cmljID0gInJvY19hdWMiKQoKZ2xtbmV0X21vZGVsIDwtIAogIGxvZ2lzdGljX3JlZygpICU+JQogIHNldF9lbmdpbmUoImdsbW5ldCIsIHNlZWQ9MjAyMSkgJT4lCiAgc2V0X21vZGUoImNsYXNzaWZpY2F0aW9uIikKCgoKZ2xtMyA8LSBmaXQoZ2xtbmV0X3dvcmtmbG93LCBkYXRhID0gZGZfdHJhaW4pCmBgYAoKCmBgYHtyfQp4Z2Jfc3BlYyA8LSBib29zdF90cmVlKAogIHRyZWVzID0gMTAwLCAKICB0cmVlX2RlcHRoID0gdHVuZSgpLAogIGxlYXJuX3JhdGUgPSB0dW5lKCkgICAgICAgICAgICAgICAgICAgICAgICAgIyMgc3RlcCBzaXplCikgJT4lIAogIHNldF9lbmdpbmUoInhnYm9vc3QiKSAlPiUgCiAgc2V0X21vZGUoImNsYXNzaWZpY2F0aW9uIikKCnhnYl9ncmlkIDwtIGdyaWRfbGF0aW5faHlwZXJjdWJlKAogIHRyZWVfZGVwdGgoKSwKICBsZWFybl9yYXRlKCksCiAgc2l6ZSA9IDUKKQoKeGdiX3dmIDwtIHdvcmtmbG93KCkgJT4lCiAgYWRkX2Zvcm11bGEodGFyZ2V0IH4gLikgJT4lCiAgYWRkX21vZGVsKHhnYl9zcGVjKQoKc2V0LnNlZWQoMTIzKQp2Yl9mb2xkcyA8LSB2Zm9sZF9jdihkZl90cmFpbiwgc3RyYXRhID0gdGFyZ2V0KQoKZG9QYXJhbGxlbDo6cmVnaXN0ZXJEb1BhcmFsbGVsKCkKCnNldC5zZWVkKDIzNCkKeGdiX3JlcyA8LSB0dW5lX2dyaWQoCiAgeGdiX3dmLAogIHJlc2FtcGxlcyA9IHZiX2ZvbGRzLAogIGdyaWQgPSB4Z2JfZ3JpZCwKICBjb250cm9sID0gY29udHJvbF9ncmlkKHNhdmVfcHJlZCA9IFRSVUUpCikKYmVzdF9hdWMgPC0gc2VsZWN0X2Jlc3QoeGdiX3JlcywgInJvY19hdWMiKQpmaW5hbF94Z2IgPC0gZmluYWxpemVfd29ya2Zsb3coCiAgeGdiX3dmLAogIGJlc3RfYXVjCikKbGlicmFyeSh2aXApCgpmaW5hbF94Z2IgJT4lCiAgZml0KGRhdGEgPSB2Yl90cmFpbikgJT4lCiAgcHVsbF93b3JrZmxvd19maXQoKSAlPiUKICB2aXAoZ2VvbSA9ICJwb2ludCIpCgpmaW5hbF9yZXMgPC0gbGFzdF9maXQoZmluYWxfeGdiLCBkZl9zcGxpdCkKCmNvbGxlY3RfbWV0cmljcyhmaW5hbF9yZXMpCmBgYAoKYGBge3J9CnhnYl9yZXMgJT4lCiAgY29sbGVjdF9tZXRyaWNzKCkgJT4lCiAgZmlsdGVyKC5tZXRyaWMgPT0gInJvY19hdWMiKSAlPiUKICBzZWxlY3QobWVhbiwgbXRyeTpzYW1wbGVfc2l6ZSkgJT4lCiAgcGl2b3RfbG9uZ2VyKG10cnk6c2FtcGxlX3NpemUsCiAgICAgICAgICAgICAgIHZhbHVlc190byA9ICJ2YWx1ZSIsCiAgICAgICAgICAgICAgIG5hbWVzX3RvID0gInBhcmFtZXRlciIKICApICU+JQogIGdncGxvdChhZXModmFsdWUsIG1lYW4sIGNvbG9yID0gcGFyYW1ldGVyKSkgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAwLjgsIHNob3cubGVnZW5kID0gRkFMU0UpICsKICBmYWNldF93cmFwKH5wYXJhbWV0ZXIsIHNjYWxlcyA9ICJmcmVlX3giKSArCiAgbGFicyh4ID0gTlVMTCwgeSA9ICJBVUMiKQpgYGAKCmBgYHtyfQoiaHR0cHM6Ly9jdXJzby1yLmdpdGh1Yi5pby90cmVlc25pcC9pbmRleC5odG1sIgpsaWJyYXJ5KHRyZWVzbmlwKQpgYGAK